LeetCode Best Time to Buy and Sell Stock IV

时间:2021-09-09 18:53:08

原题链接在这里: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情况.