LeetCode 123株式売買のベストタイミングIII HERODINGLeetCodeの道

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

1 <= prices.length <= 105
0 <= prices[i] <= 105

これは単純化された動的計画思想であり、総じて4つの状態に分けられ、それぞれその日に初めて株を買うことで得られる最大収益であり、その日に初めて株を売ることで得られる最大収益であり、その日に2回目の株を買うことで得られる最大収益であり、その日に2回目の株を売ることで得られる最大収益である.次の4つのステータスを更新します.

class Solution {
     
public:
    int maxProfit(vector<int>& prices) {
     
        int buy1 = INT_MIN;
        int sell1 = 0;
        int buy2 = INT_MIN;
        int sell2 = 0;
        // buy1:                    
        // sell1:                   
        // buy2:                   
        // sell2:                   
        //               ,   sell2    
        //    (sell2 >= sell1)
        for(int p : prices) {
     
            buy1 = max(buy1, -p);
            sell1 = max(sell1, buy1 + p);
            buy2 = max(buy2, sell1 - p);
            sell2 = max(sell2, buy2 + p); 
        }
        return sell2;
    }
};


/*  ：heroding
  ：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/solution/dong-tai-gui-hua-de-jian-hua-ban-by-hero-2mwr/
  ：  （LeetCode）
        。             ，          。*/