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; i<prices.length; i++){
if(prices[i]>prices[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; i<prices.length; i++){
if(prices[i]>prices[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<lowPrice.length; i++) lowPrice[i]=Integer.MAX_VALUE;
for(int p : prices){
for(int i=k; 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];
}