买卖股票的最佳时机iii

利用两个dp数组

• dp1[i]表示以第i个元素结尾的子串的最大收益
• dp2[i]表示以第i个元素开始的子串的最大收益

代码如下：

//
// Created by jt on 2020/9/24.
//
#include <vector>
using namespace std;

class Solution {
public:
    /**
     *
     * @param prices int整型vector
     * @return int整型
     */
    int maxProfit(vector<int>& prices) {
        // write code here
        vector<int> dp1(prices.size(), 0);
        vector<int> dp2(prices.size(), 0);
        int currentMin = prices[0];
        for (int i = 1; i < prices.size(); ++i) {
            if (prices[i] < currentMin) currentMin = prices[i];
            else dp1[i] = max(dp1[i-1], prices[i] - currentMin);
        }
        int currentMax = prices[prices.size()-1];
        for (int i = prices.size()-2; i >= 0; --i) {
            if (prices[i] > currentMax) currentMax = prices[i];
            else dp2[i] = max(dp2[i+1], currentMax - prices[i]);
        }
        int res = 0;
        for (int i = 0; i < dp1.size(); ++i) {
            res = max(res, dp1[i]+dp2[i]);
        }
        return res;
    }
};