Best Time to Buy and Sell Stock III

Question

  1. Say you have an array for
  2. which the ith element is the price of a given stock on day i.
  4. Design an algorithm to find the maximum profit.
  5. You may complete at most two transactions.
  7. Example
  8. Given an example [4,4,6,1,1,4,2,5], return 6.
  10. Note
  11. You may not engage in multiple transactions at the same time
  12. (ie, you must sell the stock before you buy again).

题解

与前两道允许一次或者多次交易不同，这里只允许最多两次交易，且这两次交易不能交叉。咋一看似乎无从下手，我最开始想到的是找到排在前2个的波谷波峰，计算这两个差值之和。原理上来讲应该是可行的，但是需要记录 O(n^2) 个波谷波峰并对其排序，实现起来也比较繁琐。

除了以上这种直接分析问题的方法外，是否还可以借助分治的思想解决呢？最多允许两次不相交的交易，也就意味着这两次交易间存在某一分界线，考虑到可只交易一次，也可交易零次，故分界线的变化范围为第一天至最后一天，只需考虑分界线两边各自的最大利润，最后选出利润和最大的即可。

这种方法抽象之后则为首先将 [1,n] 拆分为 [1,i] 和 [i+1,n], 参考卖股票系列的第一题计算各自区间内的最大利润即可。[1,i] 区间的最大利润很好算，但是如何计算 [i+1,n] 区间的最大利润值呢？难道需要重复 n 次才能得到？注意到区间的右侧 n 是个不变值，我们从 [1, i] 计算最大利润是更新波谷的值，那么我们可否逆序计算最大利润呢？这时候就需要更新记录波峰的值了。逆向思维大法好！Talk is cheap, show me the code!

Python

  1. class Solution:
  2.     """
  3.     @param prices: Given an integer array
  4.     @return: Maximum profit
  5.     """
  6.     def maxProfit(self, prices):
  7.         if prices is None or len(prices) <= 1:
  8.             return 0
  10.         n = len(prices)
  11.         # get profit in the front of prices
  12.         profit_front = [0] * n
  13.         valley = prices[0]
  14.         for i in xrange(1, n):
  15.             profit_front[i] = max(profit_front[i - 1], prices[i] - valley)
  16.             valley = min(valley, prices[i])
  17.         # get profit in the back of prices, (i, n)
  18.         profit_back = [0] * n
  19.         peak = prices[-1]
  20.         for i in xrange(n - 2, -1, -1):
  21.             profit_back[i] = max(profit_back[i + 1], peak - prices[i])
  22.             peak = max(peak, prices[i])
  23.         # add the profit front and back
  24.         profit = 0
  25.         for i in xrange(n):
  26.             profit = max(profit, profit_front[i] + profit_back[i])
  28.         return profit

C++

  1. class Solution {
  2. public:
  3.     /**
  4.      * @param prices: Given an integer array
  5.      * @return: Maximum profit
  6.      */
  7.     int maxProfit(vector<int> &prices) {
  8.         if (prices.size() <= 1) return 0;
  10.         int n = prices.size();
  11.         // get profit in the front of prices
  12.         vector<int> profit_front = vector<int>(n, 0);
  13.         for (int i = 1, valley = prices[0]; i < n; ++i) {
  14.             profit_front[i] = max(profit_front[i - 1], prices[i] - valley);
  15.             valley = min(valley, prices[i]);
  16.         }
  17.         // get profit in the back of prices, (i, n)
  18.         vector<int> profit_back = vector<int>(n, 0);
  19.         for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) {
  20.             profit_back[i] = max(profit_back[i + 1], peak - prices[i]);
  21.             peak = max(peak, prices[i]);
  22.         }
  23.         // add the profit front and back
  24.         int profit = 0;
  25.         for (int i = 0; i < n; ++i) {
  26.             profit = max(profit, profit_front[i] + profit_back[i]);
  27.         }
  29.         return profit;
  30.     }
  31. };

Java

  1. class Solution {
  2.     /**
  3.      * @param prices: Given an integer array
  4.      * @return: Maximum profit
  5.      */
  6.     public int maxProfit(int[] prices) {
  7.         if (prices == null || prices.length <= 1) return 0;
  9.         // get profit in the front of prices
  10.         int[] profitFront = new int[prices.length];
  11.         profitFront[0] = 0;
  12.         for (int i = 1, valley = prices[0]; i < prices.length; i++) {
  13.             profitFront[i] = Math.max(profitFront[i - 1], prices[i] - valley);
  14.             valley = Math.min(valley, prices[i]);
  15.         }
  16.         // get profit in the back of prices, (i, n)
  17.         int[] profitBack = new int[prices.length];
  18.         profitBack[prices.length - 1] = 0;
  19.         for (int i = prices.length - 2, peak = prices[prices.length - 1]; i >= 0; i--) {
  20.             profitBack[i] = Math.max(profitBack[i + 1], peak - prices[i]);
  21.             peak = Math.max(peak, prices[i]);
  22.         }
  23.         // add the profit front and back
  24.         int profit = 0;
  25.         for (int i = 0; i < prices.length; i++) {
  26.             profit = Math.max(profit, profitFront[i] + profitBack[i]);
  27.         }
  29.         return profit;
  30.     }
  31. };

源码分析

整体分为三大部分，计算前半部分的最大利润值，然后计算后半部分的最大利润值，最后遍历得到最终的最大利润值。

复杂度分析

三次遍历原数组，时间复杂度为 O(n), 利用了若干和数组等长的数组，空间复杂度也为 O(n).

Reference

  • soulmachine 的卖股票系列