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.

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

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

Solution I: 2D DP, TLE

The local array tracks maximum profit of j transactions & the last transaction is on ith day. The global array tracks the maximum profit of j transactions until ith day.

public class Solution { public int maxProfit(int k, int[] prices) { if (prices.length == 0) { return 0; } // solve the TLE problem if(k>=prices.length/2){ int maxProfit = 0; for(int i=1; iprices[i-1]) maxProfit += prices[i]-prices[i-1]; } return maxProfit; } int[][] res = new int[prices.length][k+1]; int[][] local = new int[prices.length][k+1]; for (int j = 1; j <= k; j++) { for (int i = 1; i < prices.length; i++) { int diff = prices[i] - prices[i-1]; local[i][j] = Math.max(res[i-1][j-1] + Math.max(diff, 0), local[i-1][j] + diff); res[i][j] = Math.max(res[i-1][j], local[i][j]); } } return res[prices.length-1][k]; } }

Solution II: General version of Best Time to Buy and Sell Stock III

https://leetcode.com/discuss/69340/clean-java-dp-o-nk-solution-with-o-k-space

public int maxProfit(int k, int[] prices) { if(k>=prices.length/2){ int maxProfit = 0; for(int i=1; iprices[i-1]) maxProfit += prices[i]-prices[i-1]; } return maxProfit; } int[] maxProfit = new int[k+1]; int[] lowPrice = new int[k+1]; for(int i=0; i=1; i--){ maxProfit[i] = Math.max(maxProfit[i],p-lowPrice[i]); lowPrice[i] = Math.min(lowPrice[i],p-maxProfit[i-1]); } } return maxProfit[k]; }