首页 > 代码库 > Best Time to Buy and Sell Stock III
Best Time to Buy and Sell Stock III
https://oj.leetcode.com/problems/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).
解题思路：
首先想到，按照Best Time to Buy and Sell Stock问题的解法，找到一个最大的区间，然后再找第二大的区间，这个第二大区间必然不能和第一大区间重合，于是便多了一个变量buyDay来记录，除此之外还多了好几个变量。但是，这个方法是错误的。为什么？因为对于可以买卖两次的问题，Best Time to Buy and Sell Stock问题的最大区间，在这里，有时候还不如分开来核算。想想，例如，6，1，3，2，4，7.问题一的最大区间为1-7=6.如果分开两次，1-3+2-7=7.所以以下代码是错误的，而且也不太容易理解。
public class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; int secondMaxProfit = 0; int profit = 0; int thisTimeMaxProfit = 0; int buyDay = 0; int maxBuyDay = 0; int buyValue; if(prices.length == 0){ return 0; }else { buyValue = prices[0]; buyDay = 0; } for(int i = 0; i < prices.length; i ++){ profit = prices[i] - buyValue; if(profit > maxProfit){ maxProfit = profit; maxBuyDay = buyDay; } //更新一个同一个买天的最大值，即local，不是global的最大利润 if(profit > thisTimeMaxProfit){ thisTimeMaxProfit = profit; } //出现新的最低买价，既要看看，这个local区间内的最大利润，即thisTimeMaxProfit，是不是可以作为第二大利润 //所以还要判断买天是不是和最大利润为一天，防止重复 if(prices[i] < buyValue){ if(thisTimeMaxProfit > secondMaxProfit && thisTimeMaxProfit <= maxProfit && buyDay != maxBuyDay){ secondMaxProfit = thisTimeMaxProfit; } buyValue = prices[i]; buyDay = i; profit = 0; thisTimeMaxProfit = 0; } //在最后一天，如果价格一直上扬，碰不到一个新买点，也要更新第二大利润 if(i == prices.length - 1 && buyDay != maxBuyDay){ if(thisTimeMaxProfit > secondMaxProfit && thisTimeMaxProfit <= maxProfit){ secondMaxProfit = thisTimeMaxProfit; } } } return maxProfit + secondMaxProfit; }}
于是出现了下面的解法。因为两次交易必然不会重合的，肯定被第k天分割在左右。所以遍历整个区间，以每天作为分割，求出左右两个区间的最大利润，再将这一对对利润相加，求出总利润中最大的。但是，这个代码的时间复杂度要O(n^2)，超时。
public class Solution { public int maxProfit(int[] prices) { int maxProfit = 0; int profit = 0; int buyValue; int leftMaxProfit = 0; int rightMaxProfit = 0; if(prices.length == 0){ return 0; }else { buyValue = prices[0]; } for(int i = 0; i < prices.length; i ++){ profit = prices[i] - buyValue; if(profit > maxProfit){ maxProfit = profit; } if(prices[i] < buyValue){ buyValue = prices[i]; profit = 0; } } for(int i = 0; i < prices.length; i ++){ buyValue = prices[0]; for(int j = 0; j < i; j++){ profit = prices[j] - buyValue; if(profit > leftMaxProfit){ leftMaxProfit = profit; } if(prices[i] < buyValue){ buyValue = prices[j]; profit = 0; } } buyValue = prices[i]; for(int k = i; k < prices.length; k++){ profit = prices[k] - buyValue; if(profit > rightMaxProfit){ rightMaxProfit = profit; } if(prices[i] < buyValue){ buyValue = prices[k]; profit = 0; } } if(leftMaxProfit + rightMaxProfit > maxProfit){ maxProfit = leftMaxProfit + rightMaxProfit; } } return maxProfit; }}
我们只好用空间换时间，分开执行两次遍历，但用两个数组，分别记录从左和从右开始的最大利润，最后将两者相加，再次遍历求出总利润最大的。
public class Solution { public int maxProfit(int[] prices) { int profit = 0; int buyValue; int sellValue; int[] leftMaxProfit = new int[prices.length]; int[] rightMaxProfit = new int[prices.length]; int[] maxProfit = new int[prices.length]; int maxProfitAll = 0; if(prices.length == 0){ return 0; }else { buyValue = prices[0]; } for(int i = 1; i < prices.length; i++){ //这里必须注意dp中状态转化方程，不可写为leftMaxProfit[i] = prices[i] - buyValue //考虑一下，已经过了最大利润区间，利润开始下降，但是该区间内的local最大利润仍然是前面的那个最大值 //所以要在leftMaxProfit[i - 1]和当前值取最大 leftMaxProfit[i] = Math.max(leftMaxProfit[i - 1], prices[i] - buyValue); if(prices[i] < buyValue){ buyValue = prices[i]; } } if(prices.length == 0){ return 0; }else { sellValue = prices[prices.length - 1]; } for(int i = prices.length - 2; i >= 0; i--){ rightMaxProfit[i] = Math.max(rightMaxProfit[i + 1], sellValue - prices[i]); if(prices[i] > sellValue){ sellValue = prices[i]; } } for(int i = 0; i < prices.length; i++){ maxProfit[i] = leftMaxProfit[i] + rightMaxProfit[i]; } for(int i = 0; i < prices.length; i++){ maxProfitAll = Math.max(maxProfitAll, maxProfit[i]); } return maxProfitAll; }}
总结：
从左往右 dp[i+1] = max{dp[i], prices[i+1] - minprices} ,minprices是区间[0,1,2...,i]内的最低价格
从右往左 dp[i -1] = max{dp[i], maxprices - prices[i-1]} ,maxprices是区间[i,i+1,...,n-1]内的最高价格。
Best Time to Buy and Sell Stock III