This is from leetcode, Best Time to Buy and 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.
The answer is to use dynamic programming by local and global 2-dimension array to implement dynamic programming:
local[i][j] = max{local[i-1][j]+diff, global[i-1][j-1]+max(diff,0)}
global[i][j] = max{local[i][j], global[i-1][j]}
local[i][j] means we do at most jth transaction at i price. If we already got the max profit at most jth transaction at i-1 price, for local[i][j], we just add price[i]-price[i-1], no matter if it is negative or positive. Another option for local[i][j] is that we get it from global[i-1][j-1]+max(diff,0). If diff is less than 0, we then ignore the transaction price[i]-price[i-1]
global[i][j] could be got from local[i][j] or global[i-1][j], which is easy to understand.
Check my code on github: link