分类
C++ Develop 算法

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

和前两道题比起来的话,这道题最难了,因为限制了交易次数。
解决问题的途径我想出来的是:既然最多只能完成两笔交易,而且交易之间没有重叠,那么就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;
    }
};

“LeetCode题目:Best Time to Buy and Sell Stock III,一维动态规划”上的46条回复

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

感觉还是有点问题吧, 假设第一个最大收益是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。

不是你说的那样。
算法并不是先确定了[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

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

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

采用楼主的方法的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;
}

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

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

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

[…] 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) […]

[…] 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) […]

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

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

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

举个例子: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个碟子的问题
这样计算每次计算都可以查阅前面计算的结果就好了,不用多次计算。

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

[…] 思路:一开始的想法是,把10中的代码拿过来稍作修改,然后将数组分割成[0…i]和[i…n-1]两个部分,最大收益就是两个部分最大收益之和(每个部分进行一次交易)。遍历 i 找出最大的。但是这样太耗时间了,后来看到uniEagle提供的思路,才恍然大悟。其实10中找出一段时间[i…j]内最大收益的过程就已经解决了[i…k]的子问题,只要维护两个一维数组,一个记录[0…i]的最大收益,一个记录[i…n-1]的最大收益即可。这两个数组都是可以在一次遍历中得出的。然后再考虑两个部分收益之和。 […]

发表评论

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