[LeetCode] 122. Best Time to Buy and Sell Stock II

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

解题想法

这题我是看其他人的解法，我卡在要怎么放弃之前买的股票

初始化 cur_hold = -float('inf') 的原因在于第一天我们不能出售股票，因为之前还没买过

整个过程分为两个状态

若我们要卖掉股票，会有 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