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).

原问题链接：https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

 

问题分析

　　这个问题里和前面的问题有不一样的地方， 在之前的问题里主要是针对一个时间段的价格变化做一次交易，那么我们的实现里只需要找到当前值和之前最小值之间的差，并取出其中最大的那个就可以了。但是这里的情况稍微不同，因为它这里是可以最多可以交易两次。也就是说，为了获取到这个最大值，我们可以交易一次，也可以交易两次。

　　那么，在实际的价格变化曲线里，可能有很多种情况。可能在序列里只有一个递增的情况，比如序列: 10, 9, 8, 20。这个时候我们能取得的最大的价值就是20 - 8。也就是说这里只需要一次交易就可以得到最理想的结果。也可能有多个变化的序列，比如说5, 6, 4, 8。这个时候我们取6 -5，再加上8 - 4这两次交易的结果，可以得到最佳结果。所以说，上面这个问题的难点就在于怎么去选择和利用好这最多两次的交易。

　　要解决这个问题，有一个需要利用的地方。就是如果我们最坏的情况是要两次交易的话，该怎么把之前一次的交易给保存起来以方便比较呢？在之前只允许一次交易的问题解决方案中，其实给了我们一个思路。这个思路是每次取到当前位置为止最小的元素，再将当前元素和这个最小值相减，再通过和之前这些差值的最大进行比较，取出最大的这个作为到当前这个位置一次交易所能获得的最大利益。那么，在实现的时候，我们可以声明一个和价格数组一样长度的列表，记录每次访问到当前位置所能取得的最大利益。这部分的实现如下：

 

        int len = prices.length, result = 0;
        int low = prices[0], high = prices[len - 1];
        int[] profitsHistory = new int[len];
        for(int i = 0; i < len; i++) {
            low = Math.min(low, prices[i]);
            result = Math.max(result, prices[i] - low);
            profitsHistory[i] = result;
        }

　　现在，剩下的部分就是怎么去比较和找最大的利益值了。我们从prices列表的最后往前，每次比较和取当前最大的价格值，再用这个值减去当前值，这个时候取得的值相当于是从最后到当前元素所能取得的最大利益值，在把这个值加上当前profitsHistory[i] 的，就是我们最多交易两次可能取得的最大值了。每次我们取它们中间最大的值保存起来。这样我们就能找到最多交易两次所能得到的最大值。

　　详细的代码实现如下：

 

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length < 2) return 0;
        int len = prices.length, result = 0;
        int low = prices[0], high = prices[len - 1];
        int[] profitsHistory = new int[len];
        for(int i = 0; i < len; i++) {
            low = Math.min(low, prices[i]);
            result = Math.max(result, prices[i] - low);
            profitsHistory[i] = result;
        }
        for(int i = len - 1; i >= 0; i--) {
            high = Math.max(high, prices[i]);
            result = Math.max(result, high - prices[i] + profitsHistory[i]);
        }
        return result;
    }
}