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.
一刷
dynamic programming
public class Solution {
public int maxProfit(int k, int[] prices) {
int len = prices.length;
if(len == 0 || k<=0) return 0;
if(k >= len/2) return greedy(prices);
int[] hold = new int[k];
int[] sold = new int[k];
Arrays.fill(hold, -prices[0]);
int max = 0;
for(int i=1; i<prices.length; i++){
for(int j = k-1; j>0; j--){
sold[j] = Math.max(sold[j], prices[i] + hold[j]);
hold[j] = Math.max(hold[j], sold[j-1] - prices[i]);
}
sold[0] = Math.max(sold[0], prices[i] + hold[0]);
hold[0] = Math.max(hold[0], -prices[i]);
}
return sold[k-1];
}
private int greedy(int[] prices){
int res = 0;
for(int i=1; i<prices.length; i++){
if(prices[i]>prices[i-1]) res += prices[i] - prices[i-1];
}
return res;
}
}
