Question

Formatted question description: https://leetcode.ca/all/123.html

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

Find the maximum profit you can achieve. You may complete at most two transactions.

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

Example 1:

Input: prices = [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 = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 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: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Constraints:

1 <= prices.length <= 10⁵
0 <= prices[i] <= 10⁵

Algorithm

Define local[i][j] as the maximum profit that can be made at most j transactions on the i-th 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 i-th 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[i-1][j-1] + max(diff, 0), local[i-1][j] + diff)

global[i][j] = max(local[i][j], global[i-1][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

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;
        }
    }
}

############

public class Solution {
    public int MaxProfit(int[] prices) {
        int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
        for (int i = 1; i < prices.Length; ++i) {
            f1 = Math.Max(f1, -prices[i]);
            f2 = Math.Max(f2, f1 + prices[i]);
            f3 = Math.Max(f3, f2 - prices[i]);
            f4 = Math.Max(f4, f3 + prices[i]);
        }
        return f4;
    }
}

// OJ: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii
// 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];
    }
};

'''
-   `f1` 表示第一次买入股票后的最大利润；
-   `f2` 表示第一次卖出股票后的最大利润；
-   `f3` 表示第二次买入股票后的最大利润；
-   `f4` 表示第二次卖出股票后的最大利润。
'''
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        # 第一次买入，第一次卖出，第二次买入，第二次卖出
        f1, f2, f3, f4 = -prices[0], 0, -prices[0], 0
        for price in prices[1:]:
            f1 = max(f1, -price)
            f2 = max(f2, f1 + price)
            f3 = max(f3, f2 - price)
            f4 = max(f4, f3 + price)
        return f4


class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        if not prices:
            return 0

        # 0 to i, max profit
        left_max = [0] * len(prices)

        tmp_min = prices[0]
        for i in range(len(prices)):
            left_max[i] = max(left_max[i-1], prices[i]-tmp_min) if i > 0 else 0
            tmp_min = min(tmp_min, prices[i])

        # i to end, max profit
        right_max = [0] * len(prices)

        tmp_max = prices[-1]
        for i in range(len(prices)-1, -1, -1):
            right_max[i] = max(right_max[i+1], tmp_max-prices[i]) if i < len(prices)-1 else 0
            tmp_max = max(tmp_max, prices[i])

        return max(left_max[i] + right_max[i] for i in range(len(prices)))

############

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)

func maxProfit(prices []int) int {
    f1, f2, f3, f4 := -prices[0], 0, -prices[0], 0
    for i := 1; i < len(prices); i++ {
        f1 = max(f1, -prices[i])
        f2 = max(f2, f1 + prices[i])
        f3 = max(f3, f2 - prices[i])
        f4 = max(f4, f3 + prices[i])
    }
    return f4
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

public class Solution {
    public int MaxProfit(int[] prices) {
        int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;
        for (int i = 1; i < prices.Length; ++i)
        {
            f1 = Math.Max(f1, -prices[i]);
            f2 = Math.Max(f2, f1 + prices[i]);
            f3 = Math.Max(f3, f2 - prices[i]);
            f4 = Math.Max(f4, f3 + prices[i]);
        }
        return f4;
    }
}

123 - Best Time to Buy and Sell Stock III

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions