[LeetCode] Best Time to Buy and Sell Stock I, II and III

By Steven
02/18/2014
C++
3

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.

I: If you were only permitted to complete at most one transaction
这个非常简单,扫一遍记录下当前最小价格,以及当前能获得的最大利润就行。
这里有个小小的代码风格问题,有人喜欢把minPrice设为数组第一个数,然后从数组第二个数开始迭代,我就喜欢设成INT_MAX, 可以看到我这样就不用判断数组是否为空,但是需要从数组第一个数开始迭代。

II: You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
这个需要想通的一点就是,假设股票每天都在涨价,那么每天买入/隔天卖出的总收益,是和第一天买入最后一天卖出的收益等价的。假设股票跌价了的话(第i+1天的价格比第i天的高),那就不买,就不计入总收益了。(一开始比较糊涂,一直在想跌价的时候要等到跌到最低再买入等问题,后来发现这其实根本就不是买股票的问题,股票哪有预先就知道接下来30天的价格的!所以所有的股票策略都不适用啊)

III: You may complete at most two transactions, but you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
第三题必须要读清题,题目说是最多可以完成两笔交易,就是说买入2次卖出2次,并且买第2次之前必须卖掉第一次买的(我一开始还想复杂了,忽略了这个条件)。 既然买入第二次之前必须卖掉第一次买的,那么实际上问题就变成了我需要找到一个i,使得0到i天内那笔交易的最大收益与i到n-1天内那笔交易的最大收益之和最大。这样的话每个单独区间的最大收益在问题I中就已经解决了。接下来就需要考虑效率问题,这里有个神奇的地方是参考别人来的(Link)。 我第一遍的代码特别蛋疼,是O(n^2)的,而这个神奇的方法是O(n)。 这里需要扫三遍:
第一遍从前往后扫,得出在第i天之前进行的那笔交易一共能赚多少
第二遍从后往前扫,注意第i天到第n天最多能赚多少,反过来就是从第n天倒回去到第i天最多能亏多少
第三遍扫之前存下的俩数组,得出最大利润

Comments: 3

  1. 不希 says:

    请保持健康的生物钟!!

  2. Jerk says:

    参看网址,只需要两次扫描,并且空间复杂度为O(1)

  3. class Solution {
    public:
    int maxProfit(vector &prices) {
    // 空间负杂度为O(1),时间复杂度为O(n)
    if(prices.size()<=1)
    return 0;
    int minPriceIndex=0,maxPriceIndex=0;
    int maxPro=0,maxTemp=0,curPriceIndex=0,curMinPriceIndex=0;
    // 首先找出只做一次交易最大的收益maxPro,并记录买入时下标minPriceIndex和卖出时下标maxPriceIndex
    for(int i=1;i<>
    {
    maxTemp+=prices[i]-prices[curPriceIndex];
    curPriceIndex=i;
    if(maxTempmaxPro)
    {
    maxPro=maxTemp;
    minPriceIndex=curMinPriceIndex;
    maxPriceIndex=i;
    }
    }
    // 在买入下标minPriceIndex之前最大的收益maxProAhead
    int maxProAhead=0,curMinPriceAhead=prices[0];
    for(int i=1;i<>
    {
    maxProAhead=max(maxProAhead,prices[i]-curMinPriceAhead);
    curMinPriceAhead=min(prices[i], curMinPriceAhead);
    }
    // 再卖出下标maxPriceIndex之后最大的收益maxProBehind
    int maxProBehind=0;
    if(maxPriceIndex+1<>
    {
    int curMinPriceBehind=prices[maxPriceIndex+1];
    for(int i=maxPriceIndex+1;i<>
    {
    maxProBehind=max(maxProBehind,prices[i]-curMinPriceBehind);
    curMinPriceBehind=min(prices[i], curMinPriceBehind);
    }
    }
    // 再买入之后到卖出之前,最大的跌幅minProMid
    int minProMid=0,curMaxPrice=prices[minPriceIndex];
    for(int i=minPriceIndex+1;i(max2>max3?max2:max3)?max1:(max2>max3?max2:max3);

    }
    };

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: