DSA

Stock trading DP: a state machine over days

Turn the facts that change your legal moves into states, and update each state's best balance or count from the previous day.

3,668 words · 17 min read

Part 1 of 10 Stock trading DP

Stock trading DP

In the stock trading problems, the input is a list of prices, one for each day, and on each day we may buy, sell or wait. To know what we may do next, we need to remember very little about the past, such as whether we own a share right now. Stock trading DP keeps one number for each of these few situations after each day: the largest balance, money received minus money paid, that we can have at that point if we end the day in that situation. The first problem charges a fee on every trade.

prices[i] is the price of one share on day ii, and every completed trade, a purchase followed by a sale, costs fee. You may hold at most one share at a time, so you must sell before you buy again, and you may make as many trades as you like. Return the largest total profit.

Constraints

  • 1≤1 \le prices.length ≤5⋅104\le 5 \cdot 10^4
  • 1≤1 \le prices[i] <5⋅104< 5 \cdot 10^4
  • 0≤0 \le fee <5⋅104< 5 \cdot 10^4

Sample 1 · Input

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

Output

8

Sample 2 · Input

prices = [1,3,7,5,10,3], fee = 3

Output

6

In the first sample, the best plan buys at 1 and sells at 8, then buys at 4 and sells at 9:

(8−1−2)+(9−4−2)=5+3=8\begin{aligned} (8 - 1 - 2) + (9 - 4 - 2) &= 5 + 3 \\ &= 8 \end{aligned}

The two plans that come to mind first both earn less. If we treat each rise as its own trade, 1 to 3, 2 to 8 and 4 to 9, we pay three fees and earn 0+4+3=70 + 4 + 3 = 7. If we make one long trade from 1 to 9, we earn 9−1−2=69 - 1 - 2 = 6. Both plans are greedy: each follows a fixed rule on the spot, without working out what a trade leaves for the days after it. The best plan joins the first two rises into one trade and keeps the last one apart, and which rises to join depends on the fee. With a fee of 5 on the same prices, the single long trade earns 9−1−5=39 - 1 - 5 = 3 and beats every split.

Trying every plan is far too slow. We call the sequence of actions taken so far a history. Each day we either change position or stay, so nn days allow up to 2n2^n histories. Here nn can be 50,000, and 2500002^{50000} is a number with 15,052 digits.