LeetCode题目:Best Time to Buy and Sell Stock III,一维动态规划

By | 2012 年 12 月 5 日

和前两道题比起来的话,这道题最难了,因为限制了交易次数。
解决问题的途径我想出来的是:既然最多只能完成两笔交易,而且交易之间没有重叠,那么就divide and conquer。
设i从0到n-1,那么针对每一个i,看看在prices的子序列[0,…,i][i,…,n-1]上分别取得的最大利润(第一题)即可。
这样初步一算,时间复杂度是O(n2)。


改进:
改进的方法就是动态规划了,那就是第一步扫描,先计算出子序列[0,…,i]中的最大利润,用一个数组保存下来,那么时间是O(n)。
第二步是逆向扫描,计算子序列[i,…,n-1]上的最大利润,这一步同时就能结合上一步的结果计算最终的最大利润了,这一步也是O(n)。
所以最后算法的复杂度就是O(n)的。



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).



代码:12ms过大集合,一次性bug free,很happy

class Solution {
public:
    int maxProfit(vector &prices) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if(prices.size() <= 1)
            return 0;
            
        //stores the max profit in [0, ... , i] subarray in prices
        vector maxEndWith;
        {//build the maxEndWith.
            int lowest = prices[0];
            int maxprofit = 0;
            maxEndWith.push_back(0);
            for(int i = 1; i < prices.size(); ++i) {
                int profit = prices[i] - lowest;
                if(profit > maxprofit) {
                    maxprofit = profit;
                }
                maxEndWith.push_back(maxprofit);
                if(prices[i] < lowest) lowest = prices[i];
            }
        }
        
        int ret = maxEndWith[prices.size() - 1];
        {//reverse to see what is the maxprofit of [i, ... , n-1] subarray in prices
        //and meanwhile calculate the final result
            int highest = prices[prices.size() - 1];
            int maxprofit = 0;
            for(int i = prices.size() - 2; i >= 0; --i) {
                int profit = highest - prices[i];
                if(profit > maxprofit)  maxprofit = profit;
                int finalprofit = maxprofit + maxEndWith[i];
                if(finalprofit > ret) ret = finalprofit;
                if(prices[i] > highest) highest = prices[i];
            }
        }

        return ret;
    }
};

46 thoughts on “LeetCode题目:Best Time to Buy and Sell Stock III,一维动态规划

  1. zhongyuan

    我觉得是顺序扫描找到从0-i 最大的收益保存数组,然后逆序扫描找到最小收益,巧妙的地方就在于逆向最小收益正是i-n之间最大收益,然后divide and conquer,逆序扫描的过程就可以算出最大值,用顺序扫描的最大值减去逆序扫描最小值(负数)。得到两次最大收益。

    Reply
  2. keiutou

    感觉还是有点问题吧, 假设第一个最大收益是from i to j, where 0<=i<j<=n-1. 楼主的思路是从从j到n-1 区间找第二大的收益。
    如果第二大的收益是再0 到 i之间呢?
    eg, 2,3,4,5,1,2,3,4,5,6,7,8,4,5,6 这串数字中最大的收益区间是从1到8,而第二大的收益区间是从2到5。 我测试了楼主的代码返回最大收益是10 而不是11。

    Reply
    1. uniEagle Post author

      不是你说的那样。
      算法并不是先确定了[0,n-1]的最大,比如[i,j],然后再去找[j+1,n-1]的最大。

      而是:
      Max( MaxProfitOn[0,i] + MaxProfitOn[i+1, n-1] )这样的。是把整个数组分两段,分别找最大,看看他们的和在如何分的时候才能达到全局最大。

      所以按照你的思路,其实是这样分的:234512345678|456,找到了局部最大。
      而算法其实是这样的:尝试了所有的分割点:
      2|34512345678456,
      23|4512345678456,
      234|512345678456,
      2345|12345678456 ,这种分割能找到全局最大。
      … 省略 …
      23451234567845|6

      Reply
  3. Meiling Zhuang

    如果最多的交易次数times是个可变的呢?如果是两次,划分为[0,i-1]和[i,n-1],此时扫描两次,在代码实现上是写成两段,一段从前往后顺序扫描,一段从后往前逆序扫描,但如果是三次,四次,五次呢,觉得按照这种思路想不清楚诶

    Reply
    1. uniEagle Post author

      以三次为例,一个简单的思路是这样的:
      划分成[0, i-1]和[i, n-1]两段,在前一段上找一次最大,在后一段上找两次最大(同此题)。
      这样是O(n^2)的算法。

      Reply
  4. Jianan

    采用楼主的方法的java版本

    public int maxProfit(int[] prices) {
    if (prices.length <= 1) return 0;
    int[]D = new int[prices.length];
    int min = prices[0];
    for (int i = 1; i < prices.length; i++) {
    if (prices[i] =0; i--) {
    if (prices[i] > high) high = prices[i];
    max = Math.max(max, high-prices[i]+D[i]);
    }
    return max;
    }

    Reply
  5. Pingback: LEETCODE: Best Time to Buy and Sell Stock III | madgie

    1. TK

      不考虑效率的话,这个算法的核心想法是枚举两次交易的中间分割点,然后用一次的算法来解。三次的话就枚举三次交易中的两个分割点,分别用一次的算法来解,然后求利润最大的。

      这其中再加入一些优化就好了,比如两次就可以像帖子里说的这样优化到O(N)

      Reply
  6. 27g

    int ret = maxEndWith[prices.size() – 1];应该是 int ret = maxEndWith[maxEndWith.size() – 1];不过不影响,越界也是0

    Reply
  7. Pingback: [LeetCode] Best Time to Buy and Sell Stock I, II and III | Hao++

  8. Pingback: Hao++

    1. zxc

      第二次要用逆序的原因是因为把原来数组分成(0,i)(i+1,n),我们要把这两个数组作为单独的数组来处理,如果第二部分再接着顺序扫,是依赖前i个元素的,如果i+1开始扫,应该也可以,但是时间复杂度就上来了,你想想,应该是吧。

      Reply
  9. felicia

    写得太清晰了! 我是小弱,我转载了一下,注明了出处。谢谢楼主。

    Reply
    1. uniEagle Post author

      我也就把Leetcode刷了两遍,这是最系统的刷题了。其它就是零星刷点POJ还有和别人讨论的面试题目而已。

      Reply
    1. uniEagle Post author

      我的理解是:
      一个问题,用递归的方法去解决的时候,会有许多的子问题被计算很多次。动态规划就是将这些把问题从小往大计算,而且记录下子问题计算后的结果,这样以后需要用到子问题的结论,直接读取结果就好,不用再计算一次。

      简单的说,就是用空间换时间。

      举个例子:3个碟子的汉诺塔,记1,2,3为三个从小到大的碟子,abc是三根柱子。问题是,把123从a挪到c,那么步骤是:
      1 -> c
      2 -> b
      1 -> b
      3 -> c
      1 -> a
      2 -> c
      1 -> c
      可以看到,前3行和后三行是同一个子问题:将12从一根柱子挪到另一根。
      如果用递归去解,这个子问题会计算两次。这还只是3个碟子的情况,可以想见如果碟子数目一多起来,这种重复计算浪费的计算资源是非常多的。
      如果用动态规划,这个子问题就只需要计算一次,但是需要存储空间来记下这个问题的解。这样解决n个碟子的问题,只需要计算以下问题即可:
      1个碟子的问题
      2个碟子的问题
      3个碟子的问题

      n个碟子的问题
      这样计算每次计算都可以查阅前面计算的结果就好了,不用多次计算。

      Reply
      1. tian

        大神呀!请问你当初刷leetcode时候速度怎样啊,我感觉我现在不看答案有些题基本没有思路~~

        Reply
        1. uniEagle Post author

          也不定,有时候思路对了很快;但是如果思路不对陷入死胡同了,半天也不定做得出一道题。
          那你可能需要强迫自己别去看答案,至少自己从各种角度都实在想不出来了再去看答案。你可以在看答案之前遍历尝试一下各种方法,包括什么二分啊、动归啊、归并啊、回溯啊之类的。

          Reply
  10. daniel

    求楼主背景,在哪里高就啊,这些灵感都是咋想到的啊~~~ 太赞!想得我脑子都炸了。。。

    Reply
    1. uniEagle Post author

      谢谢来访·
      我现在是一个Remote Worker,码农··
      做的多了就会了,我也有好些题目想得一头雾水然后就去google或者百度了。

      Reply
  11. EDFWard

    这道题想了一下午没有头绪,无奈中 google 了一下结果你的两段话顿时让人有拨云见雾之感…感谢!

    Reply
      1. iverkobe

        楼主我问一个很弱的问题~leetcode程序怎么用大数据测用时?谢谢楼主!

        Reply
        1. uniEagle Post author

          Leetcode在改版之前,可以自己选择用小数据集合或者大数据集合测试,改版之后木有了。

          Reply
  12. Pingback: leetcode刷题笔录-2 | 编程·早晨

发表评论

电子邮件地址不会被公开。 必填项已用*标注