[C++] LeetCode 123. 株の売買に最適なタイミングIII

タイトル
配列があると仮定します.i番目の要素は、i日目の株の価格です.最大の利益を見つけるためのアルゴリズムを設計します.最大2つの取引を完了することができます.注意:複数の取引に同時に参加してはいけません(再購入する前に前の株を売却しなければなりません).
問題解
この問題は1~2回取引できることを要求している.maxNum[i]日目から最終日までの最大取引価格は、まず1つの配列iで表される.では、i日目を取引先とし、1つの変数保存前のi-1日の最低価格を維持し、購入または売却の2つの状況を考慮します.1、当日購入すれば前のi日の最大利益を得ることができる場合、総最大利益は当日売り利益に加えて後の最大利益となるが、ここでは後の利益を考慮する必要はなく、この場合は後の日に考慮される.2、当日の購入で前のi日の最大利益が得られない場合は、当日の販売を考慮して、総最大利益を計算します.たとえば、prices={1,2,5,3,4,6}、1日目の株価は1です.3日目の売上最大利益は(5-1)+(6-3)で、4日目の最大利益も(5-1)+(6-3)であることがわかるので、上記の1で述べたように、当日の売上の場合、現在の最大利益のみを考慮し、後のことは考慮しないと説明した.後の最大利益を合わせると、次の日に考えられるからです.

class Solution {
public:
    int maxProfit(vector& prices) {
        int n=prices.size();
        if(n<2) return 0;
        vector maxNum(n,0);
        maxNum[n-1]=prices.back();
        for(int i=n-2;i>=0;i--){
            maxNum[i]=max(prices[i],maxNum[i+1]);
        }
        int minp=prices[0],profit=0,maxprofit=0;
        for(int i=1;iprofit){
                profit=prices[i]-minp;
                maxprofit=max(maxprofit,profit);
            }
            else{
                maxprofit=max(maxprofit,profit+maxNum[i]-prices[i]);
            }
            if(minp>prices[i]) minp=prices[i];
        }
        return maxprofit;
    }
};

方法2profit[i]は、第i日に1回の取引で得られる最大収益を表し、第1回の遍歴はprofitを計算し、第2回の逆順遍歴では、2回の取引の最大利益は前のi-1日の利益に後の最大利益を加え、現在得られる最大利益コードである.

class Solution {
public:
    int maxProfit(vector& prices) {
        if(prices.empty()) return 0;
        int n=prices.size(),minprice=prices[0],maxprofit=0;
        vector profit(n,0);
        for(int i=1;i0;i--){
            res=max(res,profit[i-1]+max(0,maxprice-prices[i]));
            maxprice=max(maxprice,prices[i]);
        }
        return res;
    }
};