Question
Formatted question description: https://leetcode.ca/all/123.html
123. Best Time to Buy and Sell Stock III 最多两次交易
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 two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
Input: [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 30 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 41 = 3.
Example 2:
Input: [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 51 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are
engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
@tagarray
Algorithm
Define local[i][j]
as the maximum profit that can be made at most j transactions on the ith day and the last transaction sold on the last day, which is the local optimal.
Then we define global[i][j]
as the maximum profit that can be performed at most j transactions when the ith day is reached, which is the global optimal (not neccessarily last transaction sold on the last day). Their recurrence is:
local[i][j] = max(global[i1][j1] + max(diff, 0), local[i1][j] + diff)
global[i][j] = max(local[i][j], global[i1][j])
The local optimal value is compared to the global optimal one less traded the previous day plus a difference greater than 0, and the local optimal of the previous day plus the difference, whichever is greater, and the global optimal compares the local optimal And the previous day’s global optimal
Code
Java

public class Best_Time_to_Buy_and_Sell_Stock_III { public class Solution_cache_intermidiates_optimize { public int maxProfit(int[] prices) { if (prices == null  prices.length == 0) { return 0; } // 0 to i, max profit int[] leftMax = new int[prices.length]; int tmpMin = prices[0]; for (int i = 1; i < prices.length; i++) { // 1. I sold it the day before, but today I can only buy without selling, so the profit is the same as the previous day // 2. Or sell today, buy at the previous lowest price leftMax[i] = Math.max(leftMax[i  1], prices[i]  tmpMin); tmpMin = Math.min(tmpMin, prices[i]); } // i to end, max profit int[] rightMax = new int[prices.length]; int tmpMax = prices[prices.length  1]; for (int i = prices.length  2; i >= 0; i) { rightMax[i] = Math.max(rightMax[i + 1], tmpMax  prices[i]); tmpMax = Math.max(tmpMax, prices[i]); } int max = 0; for (int i = 1; i < prices.length; i++) { // @note: here to ensure valid transaction, // i.e. tomorrow I can sell it, and yesterday I bought it max = Math.max(max, leftMax[i] + rightMax[i]); } return max; } } }

// OJ: https://leetcode.com/problems/besttimetobuyandsellstockiii // Time: O(KN^2) // Space: O(KN) // NOTE: this will get TLE class Solution { public: int maxProfit(vector<int>& A) { if (A.empty()) return 0; int N = A.size(); vector<vector<int>> dp(3, vector<int>(N + 1)); for (int k = 1; k < 3; ++k) { for (int i = 1; i < N; ++i) { int maxVal = INT_MIN; for (int j = 0; j < i; ++j) maxVal = max(maxVal, dp[k  1][j]  A[j]); dp[k][i + 1] = max(dp[k][i], A[i] + maxVal); } } return dp[2][N]; } };

class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ buy1 = buy2 = float("inf") sell1 = sell2 = 0 for i in range(len(prices)): sell1 = max(prices[i] + buy1, sell1) buy1 = max(buy1, prices[i]) sell2 = max(sell2, prices[i] + buy2) buy2 = max(sell1  prices[i], buy2) return max(sell1, sell2)