###### tags: `LeetCode` `Dynamic Programming` `Hard`
# LeetCode #123 [Best Time to Buy and Sell Stock III](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii)
### (Hard)
給定一個數組，它的第 i 個元素是一支給定的股票在第 i 天的價格。
設計一個算法來計算你所能獲取的最大利潤。你最多可以完成 兩筆 交易。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）

---
動態規劃題。
有四種狀態, 分別為: 1. 買一, 2.買一賣一, 3. 買二賣一, 4.買二賣二。狀態1為初始狀態買入或是維持狀態一達成(states[1], -prices[i]), 狀態2由維持狀態二或是狀態1賣出股票達成(states[2],states[1]+prices[i])。由此進行for循環, 每次狀態選擇最大值, 在循環結束後比較狀態2,4中較大者即為解

---

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int states[4]={INT_MIN, 0, INT_MIN, 0};
        for(int i=0;i<prices.size();i++){
            states[0]=max(states[0], -prices[i]);
            states[1]=max(states[1], states[0]+prices[i]);
            states[2]=max(states[2], states[1]-prices[i]);
            states[3]=max(states[3], states[2]+prices[i]);
        }
        return max(states[1],states[3]);
    }
};