原题链接在这里:https://leetcode.com/problems/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).
题解:
若是k很大已经超过了prices.length的时候, 若是按照DP的方法做会浪费时间以及空间. 此时可以直接参照Best Time to Buy and Sell Stock II做法.
Let local[i][j] denotes local maximum profit of up when prices up to i, transaction up to j, the last transaction happend at i.
loacal[i][j] = Math.max(global[i-1][j-1] + Math.max(diff, 0), local[i-1][j] + diff).
global[i-1][j-1] is global maximum profit up to prices i-1, transaction up to j-1. The last transaction happen at prices[i]. If could be diff or 0.
local[i-1][j] is local maximum profit up to pricesi-1, transaction up to j. It already perform j transaction, then the stock sold at prices[i-1] must be sold at prices[i].
Time Complexity: O(prices.length * k), k是最多交易次数.
Space: O(k).
AC Java:
public class Solution {
public int maxProfit(int k, int[] prices) {
if(prices == null || prices.length == 0 || k == 0){
return 0;
}
if(k>=prices.length/2){
int res = 0;
for(int i = 1; i < prices.length; i++){
res += Math.max(0, prices[i]-prices[i-1]);
}
return res;
} int[] local = new int[k+1];
int[] global = new int[k+1];
for(int i = 1; i<prices.length; i++){
int diff = prices[i] - prices[i-1];
for(int j = k; j>=1; j--){
local[j] = Math.max(global[j-1] + Math.max(diff,0), local[j] + diff);
global[j] = Math.max(global[j], local[j]);
}
}
return global[k];
}
}
是Best Time to Buy and Sell Stock III的general情况.