Leetcode 股票问题

第一弹 入门级：

121. 买卖股票的最佳时机

只有一个股票，只涉及一笔交易，只需要找出差值最大的两个点即可，线性扫描$O(n)$

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minn = 1e8, ans = 0;
        for(auto x: prices) {
            ans = max(ans, x - minn);
            minn = min(minn, x);
        }
        return ans;
    }
};

第二弹 普通级：

122. 买卖股票的最佳时机 II

此题的升级之处在于，可以进行多笔交易

一次$[i->j]$的交易，可以拆解成$j-i$个单位交易。所以要想总的收益最大，实际上就是从这$n-1$笔单位交易中选出所有收益为正数的天

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 0; i + 1 < prices.size(); i ++ ) {
            if(prices[i + 1] - prices[i] > 0) ans += prices[i + 1] - prices[i];
        }
        return ans;
    }
};

第三弹 进阶级：

123. 买卖股票的最佳时机 III

前后缀分解，详情见https://www.acwing.com/video/1487/

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> f(n);
        int minp = 1e8;
        for(int i = 0; i < n; i ++ ) {
            f[i] = max(f[i], prices[i] - minp);
            if(i) f[i] = max(f[i - 1], f[i]);
            minp = min(minp, prices[i]);
        }
        int maxp = 0, res = 0;
        for(int i = n - 1; i >= 0; i -- ) {
            if(i) res = max(res, maxp - prices[i] + f[i - 1]);
            else res = max(res, maxp - prices[i]);
            maxp = max(maxp, prices[i]);
        }
        return res;
    }
};