Trades With Commission

Medium1-D Dynamic Programming

Problem

prices[i] is a share's price on day i. You may complete any number of buy-then-sell trades, holding at most one share at a time, but the broker charges a commission of fee for every completed trade (charged once, when you sell).

Return the maximum total profit after commissions.

Example 1

Input:
prices = [1, 3, 2, 8, 4, 9], fee = 2
Output:
8

Buy at 1, sell at 8 (+7 - 2); buy at 4, sell at 9 (+5 - 2).

Example 2

Input:
prices = [1, 3, 7, 5, 10, 3], fee = 3
Output:
6

One trade from 1 to 10 beats two trades because each pays the fee.

Constraints

  • 1 ≤ prices.length ≤ 5·10^4
  • 1 ≤ prices[i] ≤ 5·10^4
  • 0 ≤ fee ≤ 5·10^4

Hint

Show the first hint

Start from the two-state free/hold machine for unlimited trades.

Walkthrough

How to approach it

01Clarify before coding

  • Is the fee per trade or per transaction side? Once per completed buy+sell.
  • Can fee be 0? Yes; then this is the unlimited-trades problem.
  • Must I trade at all? No; 0 if nothing beats the fee.

02Brute force

Try every set of non-overlapping (buy, sell) pairs, or recurse daily with a holding flag. Memo on (day, holding) gives the DP.

Cost: Exponential without memo; O(n) states with it.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.