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

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

思路：

前后缀分解问题：枚举分界点，找到前面的满足性质的 + 后面的满足性质的。
这道题是找到最大的利润，所以就是枚举分界点，然后找到两段利润最大的和。

首先处理前段的最大利润数组，然后开始枚举分界点找到两段的最大利润。

代码：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> p(n + 1);

        for(int i = 1,minp = INT_MAX; i <= n; i++){
            p[i] = max(p[i - 1],prices[i - 1] - minp);
            minp = min(minp,prices[i - 1]);
        }
        int res = 0;
        for(int i = n ,maxp = 0;i > 0; i--){
            res = max(res,p[i - 1] + maxp - prices[i - 1]);
            maxp = max(maxp,prices[i - 1]);
        }
        return res;
    }
};