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
代码比较长,但是思路还是比较清晰,听我解释:
核心思想:
第一步:依照Best Time to Buy and Sell Stock求得最优买卖。值为maxGap,买卖点记作minInd和maxInd。
第二步:分两种情况
case1: 在最优买卖的基础上,另外加入一次有效买卖。
case2: 拆分最优买卖,即minInd在第一次买卖中,maxInd在第二次买卖中。
看着比较简单,接下来我们纠结边界情况:
case1中: 新加的一次有效买卖与最优买卖没有交集。也就是说在minInd严格之前或者maxInd严格之后。
case2中: 第一次买卖的买点和卖点均有可能为minInd,第二次买卖的卖点和卖点均有可能为maxInd。
实现:
case1很容易,就是再跑两次最优买卖,择优加入。若不存在有效买卖则记为0。
minInd前的最优买卖记为partGap1,maxInd后的最优买卖记为partGap2。
case1Result = maxGap + max(partGap1, partGap2);
case2比较麻烦,我们来详细解释一下:
简单分析可知:
两次买卖的值分别为<minLeft, prices[j]>,<prices[k], maxRight>
其中minLeft为包括minInd在内的,minInd之前的最小值。minLeft为第一次买点的值,prices[j]为第一次卖点的值。
maxRight为包括maxInd在内的,maxInd之后的最大值。prices[k]为第二次买点的值,maxRight为第二次卖点的值。
因此必须满足以下条件:
(1)minLeft所在位置<=minInd, j>=minInd
(2)k<=maxInd, maxRight所在位置>=maxInd
(3)j<=k 满足Note的条件
case2Result = prices[j]-minLeft+maxRight-prices[k]
因为minLeft和maxRight都是确定的,最大化case2Result只需要求prices[j]-prices[k]的最大值。
这个问题化归成了"最差买卖",即最优买卖问题的逆反问题,高点买入,低点卖出。
为了节省计算量,我在实现过程中,minLeft和maxRight都在case1的计算过程中附带求出来了。
需要注意的是case1是不包含边界的,因此minLeft和maxRight还应该与minInd、maxInd值权衡一下。
class Solution { public: int maxProfit(vector<int> &prices) { if(prices.empty()) return 0; //at least 1 element int maxV = prices[0]; int maxInd = 0; int minV = prices[0]; int minInd = 0; int curGap = 0; int maxGap = 0; for(vector<int>::size_type st = 1; st < prices.size(); st ++) { if(prices[st] > maxV) {//maxV is free to update maxV = prices[st]; curGap = maxV-minV; if(curGap > maxGap) { maxGap = curGap; maxInd = st; //minInd is the landmark position, changing all the time, thus cannot be determined } } else if(prices[st] < minV) {//if minV changes, all should restart minV = prices[st]; maxV = prices[st]; curGap = 0; } } //get the minInd for(vector<int>::size_type st = 0; st < prices.size(); st ++) { if(prices[maxInd]-prices[st] == maxGap) { minInd = st; break; } } //arrive here, maxGap, maxInd, minInd is needed, thus avoid changing value //case 1: the minInd~max is covered and add the 0~minInd(partGap1) or max~size-1(partGap2) maxV = prices[0]; minV = prices[0]; curGap = 0; int partGap1 = 0; //minLeft can be prices[minInd] int minLeft = prices[minInd]; for(vector<int>::size_type st = 1; st < minInd; st ++) { minLeft = min(minLeft, prices[st]); if(prices[st] > maxV) {//maxV is free to update maxV = prices[st]; curGap = maxV-minV; if(curGap > partGap1) partGap1 = curGap; } else if(prices[st] < minV) {//if minV changes, all should restart minV = prices[st]; maxV = prices[st]; curGap = 0; } } maxV = prices[maxInd+1]; minV = prices[maxInd+1]; curGap = 0; int partGap2 = 0; //if maxInd are greater than prices.size()-3, then partGap2 remains 0. int maxRight = prices[maxInd]; //maxRight initialized to prices[maxInd] for(vector<int>::size_type st = maxInd+1; st < prices.size(); st ++) { maxRight = max(maxRight, prices[st]); if(prices[st] > maxV) {//maxV is free to update maxV = prices[st]; curGap = maxV-minV; if(curGap > partGap2) partGap2 = curGap; } else if(prices[st] < minV) {//if minV changes, all should restart minV = prices[st]; maxV = prices[st]; curGap = 0; } } //arrive here, partGap2, maxRight is needed //caseResult may be either maxGap itself or adding one part int case1Result = maxGap+max(partGap1, partGap2); //case 2: i(index of minLeft<minInd)~minInd~j add k~maxInd~l(index of maxRight>k) //case2Result = prices[j]-minLeft+maxRight-prices[k], that is max(prices[j]-prices[k]) && j<=k maxV = prices[minInd]; //j minV = prices[minInd]; //k curGap = 0; maxGap = 0; //now maxGap can be changed int tmpInd = minInd; for(vector<int>::size_type st = minInd; st <= maxInd; st ++) { if(prices[st] < minV) { minV = prices[st]; curGap = maxV-minV; if(curGap > maxGap) { maxGap = curGap; tmpInd = st; //maxInd is the landmark position, changing all the time, thus cannot be determined } } else if(prices[st] > maxV) { maxV = prices[st]; minV = prices[st]; curGap = 0; } } int case2Result = maxGap-minLeft+maxRight; return max(case1Result, case2Result); } };
解法二:动态规划
使用两个数组,maxVec和minVec。
maxVec[i]表示从0到i的最优买卖值(低买高卖,为正)。需要一次从左往右遍历。
minVec[i]表示从size-1到i的最差买卖值(高买低卖,为负)。需要一次从右往左遍历。
一次遍历数组,将对应元素相减:maxVec[i]-minVec[i]的最大值即解。
稍微分析一下发现,其实minVec是不需要的,在从右往左时候的当前值minGap即为minVec[i],
直接计算maxVec[i]-minGap,用来更新结果。这样还能免去最后在数组上面的一次遍历。
class Solution { public: int maxProfit(vector<int> &prices) { if(prices.empty()) return 0; int size = prices.size(); int minLeft = prices[0]; int maxGap = 0; //maxVec[i] means the maxGap from start to i (-->) vector<int> maxVec(size, 0); int maxRight = prices[size-1]; int minGap = 0; //minVec[i] means the minGap from end to i (<--) //vector<int> minVec(size, 0); int result = 0; for(int i = 0; i < size; i ++) { if(prices[i]-minLeft > maxGap) //current is very big maxGap = prices[i]-minLeft; else if(prices[i] < minLeft) //current is very small minLeft = prices[i]; maxVec[i] = maxGap; } for(int i = size-1; i >= 0; i --) { if(prices[i]-maxRight < minGap) //current is very small minGap = prices[i]-maxRight; else if(prices[i] > maxRight) //current is very big maxRight = prices[i]; //minVec[i] = minGap; if(maxVec[i]-minGap>result) result = maxVec[i]-minGap; } return result; } };
【LeetCode】Best Time to Buy and Sell Stock III (2 solutions)
原文:http://www.cnblogs.com/ganganloveu/p/4128114.html