Loading problem…
You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k. Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times. Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
Example 1
Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: With k = 2, buy at 2 and sell at 6 (+4), then buy at 0 and sell at 3 (+3). The total profit is 4 + 3 = 7.
Example 2
Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy at 2 and sell at 4 for +2. The final price 1 comes too late to trade, so the second transaction is not used.
Example 3
Input: k = 0, prices = [1,3]
Output: 0
Explanation: With k = 0 no transactions are allowed, so the profit is 0.
Generalize the two-transaction trick to k: keep a buy and a sell value for each of the k transactions. For every price, update transaction j's buy from transaction j-1's sell, and its sell from its own buy. If k is large enough to allow a trade on every rise, fall back to the unlimited-transaction greedy sum.
Run checks all cases above. Submit evaluates all test cases.