Medium
Related Topics: Array / Dynamic Programming / Greedy
LeetCode Source

解題想法

這題我是看其他人的解法，我卡在要怎麼放棄之前買的股票

初始化 cur_hold = -float('inf') 的原因在於第一天我們不能出售股票，因為之前還沒買過

整個過程分為兩個狀態

• 持有股票 cur_hold
• 持有現金 cur_not_hold

若我們要賣掉股票，會有 cur_not_hold = max(prev_not_hold, prev_hold + price)
反之，要買股票 cur_hold = max(prev_hold, prev_not_hold - price)

每次都要以 prev_hold, prev_not_hold = cur_hold, cur_not_hold 更新當前狀態
最後返回 cur_not_hold，也就是持有現金

Python

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        cur_hold, cur_not_hold = -float('inf'), 0
        for price in prices:
            prev_hold, prev_not_hold = cur_hold, cur_not_hold
            cur_hold = max(prev_hold, prev_not_hold - price)
            cur_not_hold = max(prev_not_hold, prev_hold + price)
        return cur_not_hold

C++

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int cur_not_hold = 0, cur_hold = -float('inf');
        for (auto price : prices) {
            int prev_not_hold = cur_not_hold, prev_hold = cur_hold;
            cur_hold = max(prev_hold, prev_not_hold - price);
            cur_not_hold = max(prev_not_hold, prev_hold + price);
        }
        return cur_not_hold;
    }
};

這系列文被記錄在 Top Interview 150 Series