Best Time to Buy and Sell Stock II

122. Best Time to Buy and Sell Stock II

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

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can buy it then immediately sell it on the same day.

Find and return the maximum profit you can achieve.

Example 1:

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

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.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

• 1 <= prices.length <= 3 * 104
• 0 <= prices[i] <= 104

Analysis

​ The problem can be divided into the small problems. Suppose we have the definition of dfs(i,j) which stands for the maximum profit you can achieve at day i, j can be 0 or 1 which stands for not holding the stock and holding the stock·，,then we can deduce that

\[dfs(i,j) = \begin{cases} max(df(i-1,0), dfs(i-1,1) + s[i]) & \text{j == 0}\\ max(dfs(i-1,1), dfs(i-1,1) - s[i]) & \text{j == 1} \\ 0 & \text{i == -1 and j == 0}\\ -\infty & \text{i == -1 and j == -1} \\ \end{cases}\]

​ For example, we have a sequence [7,1,5,3,6,4] and current end index i is 0, then dfs(0, 0) is

\[dfs(0, 0) = max(dfs(-1,0), dfs(-1,1) + 7) = 0 \\ dfs(0, 1) = max(dfs(-1,1), dfs(-1,0) - 7) = -7\]

​ So the max profit we can get on day 1 is max(0, -7)=0

​ We can also deduce the DP function: \(f[i][j] = \begin{cases} max(f[i-1][0], f[i-1][1] + s[i]) & \text{j == 0} \\ max(f[i-1][1], f[i-1][0] - s[i]) & \text{j == 1} \\ 0 & \text{i == -1 and j == 0}\\ -\infty & \text{i == -1 and j == 1} \\ \end{cases}\)

\[f[i+1][j] = \begin{cases} max(f[i][0], f[i][1] + s[i]) & \text{j == 0} \\ max(f[i][1], f[i][0] - s[i]) & \text{j == 1} \\ \end{cases}\]

Solutions

1. DFS way

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        n = len(prices)
        @cache
        def dfs(i, j):
            if i < 0:
                return -inf if j else 0
            if j:
                return max(dfs(i-1, 1), dfs(i-1,0) - prices[i])
            else:
                return max(dfs(i-1, 0), dfs(i-1,1) + prices[i])
       	return dfs(n-1,0)

Input: [10,9,2,5,3,7,101,18]

output:

4

Complexity

• Time complexity: ( O(n) ), where ( n ) is the length of the array.
• Space complexity: ( O(n) ), where ( n) is the length of the array.

2. DP

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f = [[0]*2 for _ in range(n+1)]
        f[0][0] = 0
        f[0][1] = -inf
        for i, p in enumerate(prices):
            f[i+1][0] =  max(f[i][0], f[i][1] + p)
            f[i+1][1] =  max(f[i][1], f[i][0] - p)
        return f[n][0]

Input: [10,9,2,5,3,7,101,18]

output:

4

Complexity

• Time complexity: ( O(n) ), where ( n ) is the length of the array.
• Space complexity: ( O(n) ), where ( n) is the length of the array.

3. DP one dim

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        f0 = 0
        f1 = -inf
        for p in prices:
            new_f0 = max(f0, f1+p) # preserve the old one
            f1 = max(f1, f0-p)
            f0 = new_f0
        return f0

Input: [10,9,2,5,3,7,101,18]

output:

4

Complexity

• Time complexity: ( O(n) ), where ( n ) is the length of the array.
• Space complexity: ( O(1 ), where ( n) is the length of the array.