LeetCode [188] Best Time to Buy and Sell Stock IV

188. Best Time to Buy and Sell Stock IV

Hard

You are given an integer array prices where prices[i] is the price of a given stock on the ith day.

Design an algorithm to find the maximum profit. You may complete at most k transactions.

Notice that you may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

 

Constraints:

• 0 <= k <= 109
• 0 <= prices.length <= 104
• 0 <= prices[i] <= 1000

-----

• i and j are the indices of transactions and days, respectively
• when computing dp[i][j], two cases are considered
• do not sell on day j. Thus, dp[i][j] = dp[i][j-1]
• sell on day j. Thus, dp[i][j] = prices[j] + tmp. 
• in Case 2, there must be i-1 complete transactions (one buying and one selling is a complete transaction) before day j because another complete transaction must sell on day j.
• also, there must be 1 more buying than selling right before day j so that there exists a stock to sell on day j. 
• Thus, tmp is the max net income before day j. This net income has two parts:
•  the profit of i-1 complete transactions before day j
• the price to buy one more time
• when j=1, tmp = -prices[0] because there is zero complete transactions and 1 buying. 
• dp[i-1][j-1]-prices[j] is the value of tmp when this one more buying occurs on day j
• tmp = max(tmp, dp[i-1][j-1]+prices[j]) maintains the maximum value of tmp through the evolving of j.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

class Solution { public: int quickSolve(vector<int>& prices){ int maxP = 0; for(int i=1; i<prices.size(); ++i){ if(prices[i]>prices[i-1]) maxP += prices[i]-prices[i-1]; } return maxP; } int maxProfit(int k, vector<int>& prices) { int n = prices.size(); if(k>=n/2) return quickSolve(prices); vector<vector<int>> dp(k+1, vector<int>(n, 0)); for(int i=1; i<=k; ++i){ int tmp = -prices[0]; for(int j=1; j<n; ++j){ dp[i][j] = max(dp[i][j-1], prices[j]+tmp); tmp = max(tmp, dp[i-1][j-1]-prices[j]); } } return dp[k][n-1]; } }; class Solution { public: int quickSolve(vector<int> &prices){ int res = 0; int n = prices.size(); for(int i=1; i<n; ++i){ if(prices[i]>prices[i-1]){ res += prices[i]-prices[i-1]; } } return res; } int maxProfit(int k, vector<int> &prices) { int n = prices.size(); if(n==0) return 0; if(k>n/2) return quickSolve(prices); int dp[10000] = {0}; int tmpMax, dppre, dppre1; for(int s = 1; s<=k; ++s){ tmpMax = -prices[0]; dppre = dp[0]; for(int t = 1; t<n; ++t){ dppre1 = dppre; dppre = dp[t]; dp[t] = max(dp[t], dp[t-1]); dp[t] = max(dp[t], tmpMax+prices[t]); tmpMax = max(tmpMax, dppre1-prices[t]); } } return dp[n-1]; } };

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

class Solution { int quickSolve(int[] prices){ int n = prices.length; int profit = 0; for(int i=1; i<n; ++i){ if(prices[i]>prices[i-1]){ profit += prices[i]-prices[i-1]; } } return profit; } public int maxProfit(int k, int[] prices) { int n = prices.length; if(k>=n/2) return quickSolve(prices); int[] dp = new int[n]; for(int i=1; i<=k; ++i){ int tmp = -prices[0]; int[] dp1 = new int[n]; for(int j=1; j<n; ++j){ dp1[j] = Math.max(dp1[j-1], tmp+prices[j]); tmp = Math.max(tmp, dp[j-1]-prices[j]); } dp = dp1; } return dp[n-1]; } }