[LeetCode] 123. Best Time to Buy and Sell Stock III

Posted on | In

Problem

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:

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

Example 2:

1
2
3
4
5
Input: [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:

1
2
3
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.

Explanation

  1. Note that the maximum transaction is 2, and we can sell and buy on the same day. We can divide this array into two parts: prices[0:n-1] => prices[0:i] + prices[i:n-1], so we need to find the maximum of profit on or before day i, and the maximum profit on or after day i, then the result will be the sum of the two.

  2. We can solve this problem by calculating every indexes i’s mostLeftProfit and mostRightProfit, then the result will be the maximum of the sum of these two.

  3. First, we use an array to store all indexes mostLeftProfit by iterating from beginning to the end. Then, we iterate from the end back to the beginning to calculate the mostRightProfit and compare each index’s mostLeftProfit and its mostRightProfit to get the final maximum result.

Solution

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
class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int[] leftProfit = new int[n];

        int maxLeftProfit = 0, min = prices[0];
        for (int i = 1; i < n; i++) {
            if (prices[i] < min) {
                min = prices[i];
            } else {
                maxLeftProfit= Math.max(maxLeftProfit, prices[i] - min);
            }
            leftProfit[i] = maxLeftProfit;
        }

        int res = leftProfit[n-1];
        int maxRightProfit = 0, max = prices[n-1];
        for (int j = n-2; j >= 0; j--) {
            if (prices[j] > max) {
                max = prices[j];
            } else {
                maxRightProfit = Math.max(maxRightProfit, max - prices[j]);
            }
            res = Math.max(res, leftProfit[j]+maxRightProfit);
        }

        return res;
    }
}