LeetCode123.株を売買する最良のタイミングIII

タイトルの説明
配列が与えられ、i番目の要素はi日目の株価である.
あなたが得られる最大利益を計算するアルゴリズムを設計します.最大2つの取引を完了することができます.
注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
例1:
入力:[3,3,3,5,0,0,3,1,4]出力:6解釈:4日目(株価=0)に購入し、6日目(株価=3)に売却し、この取引所は利益=3-0=3を得ることができる.その後、7日目(株価=1)に購入し、8日目(株価=4)に売却し、この取引所は利益=4-1=3を得ることができる.
例2:
入力:[1,2,3,4,5]出力:4解釈:1日目(株価=1)に購入し、5日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.1日目と2日目に株を相次いで購入してから売ることはできないことに注意してください.これは同時に複数の取引に参加しているので、再購入する前に前の株を売却しなければなりません.
例3:
入力:[7,6,4,3,1]出力:0解釈:この場合、取引が完了しないため、最大利益は0である.
出典:力ボタン(LeetCode)
問題解
ダイナミックプランはまだよく分からないので、完全に理解してから補充します.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.size()==0) return 0;
        int *dp=new int[prices.size()];
        int *dp_2=new int[prices.size()];
        int ans=0;
        left(prices,dp);
        right(prices,dp_2);
        for(int i=0;i<prices.size();i++)
            ans=max(ans,dp[i]+dp_2[i]);
        return ans;

    }

    void left( vector<int> prices, int *&dp)
    {
        int ans=0;
        int low=prices[0];
        for(int i=0;i<prices.size();i++)
        {
            ans=max(ans,prices[i]-low);
            dp[i]=ans;
            low=min(low,prices[i]);
        }
    }
    void right(vector<int> prices,int *&dp)
    {
        int ans=0;
        int high=prices[prices.size()-1];
        for(int i=prices.size()-1;i>=0;i--)
        {
            ans=max(ans,high-prices[i]);
            dp[i]=ans;
            high=max(high,prices[i]);
        }
    }
};