題目

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

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

1
2
3
4
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

1
2
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.

解釋題目

給你一個 array，叫做 prices，prices 中每個值是一支股票每天的價格，跟 leetcode-121 不同的是，這題每天都可以買進跟賣出股票。也就是說，當天賣完股票，可以馬上再買進，一樣是取得最大利益。

思路 (1)

  1. 這題也可以使用雙指針解題，雙指針是左 ( left )、右 ( right ) 指針，一開始會是 left = 0 跟 right = 1
  2. 使用雙指針解題，通常用 while，條件設定是「右指針」走到底結束。
  3. 目的: 把所有 右指針的值 > 左指針的值，加總起來即可。
  4. 若 右指針的值 < 左指針的值，代表該股票沒有獲利，左右指針都要往下走一步。
  5. 此解法，時間複雜度為 O(n)，空間複雜度為 O(1)。

程式碼 (1)

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        left = 0
        right = 1
        max_profit = 0
        while right < length:
            profit = prices[right] - prices[left]
            if profit > 0:
                max_profit = max_profit + profit
            left = left + 1
            right = right + 1
        return max_profit

思路 (2)

  1. 另外也可用 「動態規劃」(Dynamic Programming) 的解法，何謂「動態規劃」(Dynamic Programming)?

    動態規劃（Dynamic Programming, DP） 是一種解決複雜問題的演算法設計方法，通過將問題拆分為更小的子問題來解決，並利用子問題的重疊性來避免重複計算。它特別適合處理具有「最優子結構」和「重疊子問題」性質的問題。

  2. 動態規劃的方法，就是要去紀錄每天結束後的最大利潤，而每天的最大利潤會有兩種情況:
    • 不持有股票
    • 持有股票
  3. 所謂的 利潤計算方式 是: 賣股票後所持有的 現金 ，以 [7, 1, 5, 3, 6, 4] 為例，如果我第一天持有股票的話，我的利潤是 -7。
  4. 所以為了記錄每天的最大利潤，首先要建立一個二維的陣列，通常叫 dp，dp = [[0, 0], [0, 0], [0, 0], [0, 0], [0, 0], [0, 0]]
  5. 動態規劃 (dp) 的狀態有兩種:
    1. dp[i][0]=> 第 i 天，「不」持有股票的最大利潤，不持有股票的情況有兩種:
      • 第 i 天賣股票，此時最大利益會是: 第 i - 1 天持有股票的最大利潤 + 第 i 天的股票價格 = dp[i-1][1] + prices[i]
      • 第 i 天不做任何交易，此時最大利益會是: 維持第 i - 1 天，「不」持有股票的最大利潤 = dp[i-1][0]
        根據這兩種情況，找出獲利最大的那一個情況，也就是 dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
    2. dp[i][1]=> 第 i 天，「持有」股票的最大利潤，持有股票的情況有兩種:
      • 第 i 天買股票，此時最大利益會是: 第 i - 1 天「不」持有股票的最大利潤 - 第 i 天的股票價格 = dp[i-1][0] - prices[i]，因為買股票手上會失去現金。
      • 第 i 天不做任何交易，此時最大利益會是: 維持第 i - 1 天，持有股票的最大利潤 = dp[i-1][1]
        根據這兩種情況，找出獲利最大的那一個情況，也就是 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1]
  6. 動態規劃很重要的核心是要有初始值，也就是 dp[0][0] 及 dp[0][1]。
  7. 最後是返回，最後一天不持有股票的最大利潤，因為一定要賣出才會獲利。

程式碼 (2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if length == 0:
          return 0

        # 建立 dp 狀態表
        dp = [[0, 0] for _ in range(length)]
        dp[0][0] = 0
        dp[0][1] = -prices[0]

        for i in range(1, length):
          # 第 i 天，「不」持有股票的最大利潤
          dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])

          # 第 i 天，「持有」股票的最大利潤
          dp[i][1] = max(dp[i-1][0] - prices[i], dp[i-1][1])
      
        # 最後一天不持有股票的狀態
        return dp[length -1][0]

思路 (3)

  1. 主要是優化思路 (2) 的解法，思路 (2) 的空間複雜度是 O(n)，因為陣列很長的話，dp 狀態表也需要很長。但實際上，我們只會依賴前一天的最大利潤數據，就可以得到下一天的最大利潤數據。
  2. 所以優化的方式，就是用變數取代整個 dp 列表。
  3. 優化後，空間複雜度會是 O(1)

程式碼 (3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        length = len(prices)
        if length == 0:
          return 0

        # 用變數取代 dp 列表
        prev0 = 0
        prev1 = -prices[0]

        for i in range(1, length):
          # 第 i 天，「不」持有股票的最大利潤
          curr0 = max(prev0, prev1 + prices[i])

          # 第 i 天，「持有」股票的最大利潤
          curr1 = max( prev0 - prices[i], prev1)

          prev0, prev1 = curr0, curr1
      
        # 最後一天不持有股票的狀態
        return prev0