# Best Time to Buy and Sell Stock III ### Source - leetcode: [Best Time to Buy and Sell Stock III | LeetCode OJ](https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/) - lintcode: [(151) Best Time to Buy and Sell Stock III](http://www.lintcode.com/en/problem/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. Example Given an example [4,4,6,1,1,4,2,5], return 6. Note You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). ~~~ ### 題解 與前兩道允許一次或者多次交易不同，這里只允許最多兩次交易，且這兩次交易不能交叉。咋一看似乎無從下手，我最開始想到的是找到排在前2個的波谷波峰，計算這兩個差值之和。原理上來講應該是可行的，但是需要記錄 O(n2)O(n^2)O(n2) 個波谷波峰并對其排序，實現起來也比較繁瑣。 除了以上這種直接分析問題的方法外，是否還可以借助分治的思想解決呢？最多允許兩次不相交的交易，也就意味著這兩次交易間存在某一分界線，考慮到可只交易一次，也可交易零次，故分界線的變化范圍為第一天至最后一天，只需考慮分界線兩邊各自的最大利潤，最后選出利潤和最大的即可。 這種方法抽象之后則為首先將 [1,n] 拆分為 [1,i] 和 [i+1,n], 參考賣股票系列的第一題計算各自區間內的最大利潤即可。[1,i] 區間的最大利潤很好算，但是如何計算 [i+1,n] 區間的最大利潤值呢？難道需要重復 n 次才能得到？注意到區間的右側 n 是個不變值，我們從 [1, i] 計算最大利潤是更新波谷的值，那么我們可否逆序計算最大利潤呢？這時候就需要更新記錄波峰的值了。逆向思維大法好！Talk is cheap, show me the code! ### Python ~~~ class Solution: """ @param prices: Given an integer array @return: Maximum profit """ def maxProfit(self, prices): if prices is None or len(prices) <= 1: return 0 n = len(prices) # get profit in the front of prices profit_front = [0] * n valley = prices[0] for i in xrange(1, n): profit_front[i] = max(profit_front[i - 1], prices[i] - valley) valley = min(valley, prices[i]) # get profit in the back of prices, (i, n) profit_back = [0] * n peak = prices[-1] for i in xrange(n - 2, -1, -1): profit_back[i] = max(profit_back[i + 1], peak - prices[i]) peak = max(peak, prices[i]) # add the profit front and back profit = 0 for i in xrange(n): profit = max(profit, profit_front[i] + profit_back[i]) return profit ~~~ ### C++ ~~~ class Solution { public: /** * @param prices: Given an integer array * @return: Maximum profit */ int maxProfit(vector<int> &prices) { if (prices.size() <= 1) return 0; int n = prices.size(); // get profit in the front of prices vector<int> profit_front = vector<int>(n, 0); for (int i = 1, valley = prices[0]; i < n; ++i) { profit_front[i] = max(profit_front[i - 1], prices[i] - valley); valley = min(valley, prices[i]); } // get profit in the back of prices, (i, n) vector<int> profit_back = vector<int>(n, 0); for (int i = n - 2, peak = prices[n - 1]; i >= 0; --i) { profit_back[i] = max(profit_back[i + 1], peak - prices[i]); peak = max(peak, prices[i]); } // add the profit front and back int profit = 0; for (int i = 0; i < n; ++i) { profit = max(profit, profit_front[i] + profit_back[i]); } return profit; } }; ~~~ ### Java ~~~ class Solution { /** * @param prices: Given an integer array * @return: Maximum profit */ public int maxProfit(int[] prices) { if (prices == null || prices.length <= 1) return 0; // get profit in the front of prices int[] profitFront = new int[prices.length]; profitFront[0] = 0; for (int i = 1, valley = prices[0]; i < prices.length; i++) { profitFront[i] = Math.max(profitFront[i - 1], prices[i] - valley); valley = Math.min(valley, prices[i]); } // get profit in the back of prices, (i, n) int[] profitBack = new int[prices.length]; profitBack[prices.length - 1] = 0; for (int i = prices.length - 2, peak = prices[prices.length - 1]; i >= 0; i--) { profitBack[i] = Math.max(profitBack[i + 1], peak - prices[i]); peak = Math.max(peak, prices[i]); } // add the profit front and back int profit = 0; for (int i = 0; i < prices.length; i++) { profit = Math.max(profit, profitFront[i] + profitBack[i]); } return profit; } }; ~~~ ### 源碼分析 整體分為三大部分，計算前半部分的最大利潤值，然后計算后半部分的最大利潤值，最后遍歷得到最終的最大利潤值。 ### 復雜度分析 三次遍歷原數組，時間復雜度為 O(n)O(n)O(n), 利用了若干和數組等長的數組，空間復雜度也為 O(n)O(n)O(n). ### Reference - soulmachine 的賣股票系列