# Buy stock to get max profit with at most K times

By | October 20, 2015
Share the joy
•
•
•
•
•
•

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