# 122 - Best Time to Buy and Sell Stock II

解法一 - Greedy

我們可以先想出幾個 greedy idea:

1. 一下跌就買進，一上漲就賣出：

   [1,2,3,4,5]這個例子就不適用，因為一上漲就賣出的話，在 2 就會賣出。

2. 在下跌趨勢的底買進，在上漲趨勢的尾賣出：

   觀察了題目中的幾個 case 後，感覺這個演算法的結果都對，於是考慮 edge 之後的實作如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int profit = 0, curPrice;
        bool bought = false;

        for(int i=0; i<prices.size(); i++) {
            if(i == prices.size()-1) {
                if(bought && prices[i] > curPrice)
                    profit += prices[i]-curPrice; 
                break;
            }

            if( prices[i] > prices[i+1] && bought) { 
                profit += prices[i]-curPrice; 
                bought = false; 
            }
            else if(prices[i] < prices[i+1] && !bought) { 
                bought = true; 
                curPrice = prices[i]; 
            }
        }

        return profit;
    }
};

解法二 -

參考 Leetcode solution 的 solution 3，這題還有更簡單的解法，其實只要把沿路上有增加的 price 都加總起來就好。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        if(prices.empty()) return 0;

        int maxprofit = 0;
        for (int i = 1; i < prices.size(); i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }

        return maxprofit;
    }
};