Best Time to Buy and Sell Stock I

只能作一次操作时：维护preMin记录之前出现的最小值

代码如下：

    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0) return 0;
        int profit = 0;
        int preMin = prices[0];
        for (int i = 1; i < prices.size(); i++)
        {
            if (prices[i] < preMin) preMin = prices[i];
            profit = max(profit, prices[i] - preMin);
        }
        return profit;
    }

能无限次操作时：当==>当前价格 > 买入价格的时候，卖出

代码如下：

    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0) return 0;
        int profit = 0;
        int buy = prices[0];
        for (int i = 1; i < prices.size(); i++)
        {
            if (buy < prices[i])
                profit += prices[i] - buy;
            buy = prices[i];
        }
        return profit;
    }

只能操作两次时：

两次操作不能重叠，可以分成两部分：0...i的最大利润fst  和i...n-1的最大利润snd

代码如下：

    int maxProfit(vector<int> &prices) {
        if (prices.size() == 0) return 0;
        int size = prices.size();
        vector<int> fst(size);
        vector<int> snd(size);
        
        int preMin = prices[0];
        for (int i = 1; i < size; i++)
        {
            if (preMin > prices[i]) preMin = prices[i];
            fst[i] = max(fst[i - 1], prices[i] - preMin);
        }
        int profit = fst[size - 1];
        int postMax = prices[size - 1];
        for (int i = size - 2; i >= 0; i--)
        {
            if (postMax < prices[i]) postMax = prices[i];
            snd[i] = max(snd[i + 1], postMax - prices[i]);
            //update profit
            profit = max(profit, snd[i] + fst[i]);
        }
        return profit;
    }

Best Time to Buy and Sell Stock I,II,III [leetcode]