[LintCode] 151 Best Time to Buy and Sell Stock III 解题报告

Description
Say you have an array for which the i^th 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.


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



Example
Given an example [4,4,6,1,1,4,2,5], return 6.



思路
最多2次买卖。
我们从左到右，在每一个i计算：
如果只能一次买卖，从第0天到第i天，能获得的最大利润是多少。
我们再从右到左，在每一个i计算：
如果只能买卖一次，从第i天到最后一天，能获得的最大利润是多少。

我们可以知道，在任何一天i，我们最多2次买卖的最大利润，是从第0天到第i天有最多1次买卖的最大利润，加上从第i天到最后一天有最多1次买卖的最大利润。



Code

class Solution {
    /**
     * @param prices: Given an integer array
     * @return: Maximum profit
     */
    public int maxProfit(int[] prices) {
        // write your code here
        
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        int[] left = new int[prices.length];
        int[] right = new int[prices.length];
        left[0] = 0;
        right[prices.length - 1] = 0;
        
        int min = prices[0];
        int max = prices[prices.length - 1];
        
        for (int i = 1; i < prices.length; i++) {
            left[i] = Math.max(left[i - 1], prices[i] - min);
            min = Math.min(min, prices[i]);
        }
        
        for (int i = prices.length - 2; i >= 0; i--) {
            right[i] = Math.max(right[i + 1], max - prices[i]);
            max = Math.max(max, prices[i]);
        }
        
        int maxProfit = 0;
        for (int i = 0; i < prices.length; i++) {
            maxProfit = Math.max(maxProfit, left[i] + right[i]);
        }
        
        return maxProfit;
    }
};