首页 > 代码库 > 【LeetCode】Best Time to Buy and Sell Stock III (2 solutions)
【LeetCode】Best Time to Buy and Sell Stock III (2 solutions)
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)