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.

接口：

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here

    }
};

分析：

这题目中谈到了两次transaction，而且要求两次transaction不overlap，所以应该认为他是一道forward-backward traversal的题目，正着找每次交易的profit，反着再找一次，最后循环所有交易看最大利润出现在哪里。

解答：

class Solution {
public:
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    int maxProfit(vector<int> &prices) {
        // write your code here
        if (prices.size() <= 1) {
            return 0;
        }

        vector<int> profitForward(prices.size() );
        vector<int> profitBackward(prices.size() );

        int minPrice = INT_MAX;
        int maxProfit = 0;
        for (int i = 0; i < prices.size(); i++) {
            minPrice = min(minPrice, prices[i]);
            maxProfit = max(maxProfit, prices[i] - minPrice);
            profitForward[i] = maxProfit;
        }

        int maxPrice = INT_MIN;
        maxProfit = 0;
        for (int j = prices.size() - 1; j >=0; j--) {
            maxPrice = max(maxPrice, prices[j]);
            maxProfit = max(maxProfit, maxPrice - prices[j]);
            profitBackward[j] = maxProfit;
        }

        int res = 0;
        for (int k = 0; k < prices.size(); k++) {
            res = max(res, profitForward[k] + profitBackward[k]);
        }

        return res;
    }
};