LeetCode 123 Best Time to Buy and Sell Stock III

Posted on | In | 阅读
  1. 维护两个变量b与s，b[i]为前i日内买入的最大剩余钱量(可以为负)。s[i]为前i日卖出后的最大钱量。
  2. s[i]由b[i]迭代而来，b[i]由前一轮的s[i]迭代而来，所以只用一轮循环就可以完成更新。

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size() == 0){
            return 0;
        }
        int b1 = -0x7fffffff, s1 = 0, b2 = -0x7fffffff, s2 = 0;
        for(int i = 0; i < prices.size(); i++){
            b1 = max(b1, -prices[i]);
            s1 = max(s1, prices[i] + b1);
            
            b2 = max(b2, s1 - prices[i]);
            s2 = max(s2, prices[i] + b2);
        }
        return s2;
    }
};