309. Best Time to Buy and Sell S

Description

Say you have an array for which the i^th element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

Input: [1,2,3,0,2]
Output: 3
Explanation: transactions = [buy, sell, cooldown, buy, sell]

Solution

DP, O(n), S(n)

The transaction sequences can end with any of these three states.
For each of them we make an array, buy[n], sell[n] and rest[n].

• buy[i] means before day i what is the maxProfit for any sequence end with buy.
• sell[i] means before day i what is the maxProfit for any sequence end with sell.
• rest[i] means before day i what is the maxProfit for any sequence end with rest.

Then we want to deduce the transition functions for buy sell and rest. By definition we have:

• buy[i] = max(rest[i-1]-price, buy[i-1])
• sell[i] = max(buy[i-1]+price, sell[i-1])
• rest[i] = max(sell[i-1], rest[i-1])

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        
        int n = prices.length;
        int[] buy = new int[n]; // buy[i]: hold stock on day i
        int[] sell = new int[n]; // sell[i]: not holding stock on day i
        int[] rest = new int[n]; // rest[i]: no transaction on day i
        buy[0] = -prices[0];
        
        for (int i = 1; i < n; ++i) {
            buy[i] = Math.max(rest[i - 1] - prices[i], buy[i - 1]);
            sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
            rest[i] = Math.max(sell[i - 1], rest[i - 1]);
        }
        
        return sell[n - 1];
    }
}

进一步分析后我们可以得知，rest[i] = sell[i - 1]，所以可以省略掉rest[]：

• buy[i] = max(sell[i - 2] - price, buy[i - 1])
• sell[i] = max(buy[i - 1] + price, sell[i - 1])

State machine, O(n), S(n)

这个解法很棒，比上面那种更清晰。

image.png

s0[i] = max(s0[i - 1], s2[i - 1]); // Stay at s0, or rest from s2
s1[i] = max(s1[i - 1], s0[i - 1] - prices[i]); // Stay at s1, or buy from s0
s2[i] = s1[i - 1] + prices[i]; // Only one way from s1

Initialization:

s0[0] = 0; // At the start, you don't have any stock if you just rest
s1[0] = -prices[0]; // After buy, you should have -prices[0] profit. Be positive!
s2[0] = INT_MIN; // Lower base case, not zero!!!

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        
        int n = prices.length;
        int[] s0 = new int[n];
        int[] s1 = new int[n];
        int[] s2 = new int[n];
        s0[0] = 0;
        s1[0] = -prices[0];
        s2[0] = Integer.MIN_VALUE;
        
        for (int i = 1; i < n; ++i) {
            s0[i] = Math.max(s2[i - 1], s0[i - 1]);
            s1[i] = Math.max(s0[i - 1] - prices[i], s1[i - 1]);
            s2[i] = s1[i - 1] + prices[i];
        }
        
        return Math.max(s0[n - 1], s2[n - 1]);
    }
}

DP, O(n), S(1)

由于dp[i]只依赖于dp[i - 1]，可以轻松降成S(1)。