[LeetCode] Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete at most two transactions.

Note:
You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

解题思路

建立两个数组left和right，分别存储某个元素左边和右边所能获得的最大收益。即left[i]存储从[0, i]范围的最大收益；right[i]存储从[i, len - 1]范围的最大收益。

实现代码

/*****************************************************************
    *  @Author   : 楚兴
    *  @Date     : 2015/2/22 18:08
    *  @Status   : Accepted
    *  @Runtime  : 16 ms
******************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int len = prices.size();
        if (len == 0)
        {
            return 0;
        }
        vector<int> left(len, 0);
        vector<int> right(len, 0);

        int i = 0;
        int low = prices[0];
        int profit = 0;
        while (i < len - 1)
        {
            if (prices[i] < low)
            {
                low = prices[i];
            }
            else if (prices[i] >= prices[i + 1])
            {
                profit = max(profit, prices[i] - low);
            }
            left[i] = profit;
            i++;
        }
        profit = max(profit, prices[i] - low);
        left[i] = profit;

        int high = prices[i];
        profit = 0;
        while(i > 0)
        {
            if (prices[i] > high)
            {
                high = prices[i];
            }
            else if (prices[i] <= prices[i - 1])
            {
                profit = max(profit, high - prices[i]);
            }
            right[i] = profit;
            i--;
        }
        profit = max(profit, high - prices[i]);
        right[i] = profit;

        i = 0;
        int max_profit = 0;
        while (i < len)
        {
            max_profit = max(max_profit, left[i] + right[i]);
            i++;
        }

        return max_profit;
    }
};

int main()
{
    int num[] = {1,2,3,4,5,6};
    vector<int> n(num, num + sizeof(num)/sizeof(int));

    Solution s;
    int profit = s.maxProfit(n);
    cout<<profit<<endl;
}

另一种解题思路可参考Best Time to Buy and Sell Stock IV。