LeetCode123. Best Time to Buy and Sell Stock III

タイトルリンク:
https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/
タイトルの説明:
1つの配列で株の毎日の価格を表し、配列のi番目の数で株のi日目の価格を表す.最大2回取引して、手の上で最大1本の株を持つことしかできなくて、最大の収益を求めます.
考え方:
最大2回の取引.i日を境界線とし、prices[i]を末尾とする最大収益(すなわち、i日以前の最大収益、移動後)、prices[i]を先頭とする最大収益(i日後の最大収益、後方)を記録することができる.preProfit[i]+postProfit[i]は全体の最大収益である.最大収益を比較して最大値を見つけます.
コード:

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0){
            return 0;
        }
        int* preProfit=new int [len];
        int* postProfit=new int [len];
        int minPrice=prices[0];
        preProfit[0]=0;
        for(int i=1;i<len;i++){
            minPrice=min(minPrice,prices[i]);
            preProfit[i]=max(preProfit[i-1],prices[i]-minPrice);
        }
        int maxPrice=prices[len-1];
        postProfit[len-1]=0;
        for(int i=len-2;i>=0;i--){
            maxPrice=max(maxPrice,prices[i]);
            postProfit[i]=max(postProfit[i+1],maxPrice-prices[i]);
        }
        int maxRes=preProfit[0]+postProfit[0];
        for(int i=1;i<len;i++){
            if(maxRes<preProfit[i]+postProfit[i]){
                maxRes=preProfit[i]+postProfit[i];
            }
        }
        return maxRes;
    }
};