首页 > 其他 > 详细

【LeetCode】Best Time to Buy and Sell Stock III (2 solutions)

时间:2014-11-28 13:56:26      阅读:329      评论:0      收藏:0      [点我收藏+]

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);
    }
};

bubuko.com,布布扣

 

解法二:动态规划

使用两个数组,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;
    }
};

bubuko.com,布布扣

【LeetCode】Best Time to Buy and Sell Stock III (2 solutions)

原文:http://www.cnblogs.com/ganganloveu/p/4128114.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!