DP #29. Best Time to Buy Sell stock IV. - mbhushan/dynpro GitHub Wiki

(29). Best Time to Buy Sell stock - IV.

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most k transactions.

Note:
You may not engage in multiple transactions at the same time 
(ie, you must sell the stock before you buy again).
Formula:

T[i][j] = Max {
                T[i][j-1], //not transacting on day j
                T[i-1][m] + price[j] - price[m] for m = 0...j-1;
};
index -> 0 1 2 3 4 5 6 7
prices -> 2 5 7 1 4 3 1 3
0 0 0 0 0 0 0 0 0
1 0 3 5 5 5 5 5 5
2 0 3 5 5 8 8 8 8
3 0 3 5 5 8 8 8 10 (ans)

Buy Sell - K Transaction

  • Time Complexity: O(n^2)
  • Space Complexity: O(n^2)