一道关于股票的算法题，和121 & 123 类似

14417335 发表于 2021-3-16 02:36
871

那么DP【第几天】【拥有多少股】= 最多的价值

“拥有多少股”要计算到n/2，时间复杂度是o(N^2)，感觉复杂度太大了。不如前面的贪心法好。

wisdompeak2 发表于 2021-3-16 21:56
“拥有多少股”要计算到n/2，时间复杂度是o(N^2)，感觉复杂度太大了。不如前面的贪心法好。

没错O (N^2 / 2)。但我还没完全接受那个贪心的思路的正确性。先后顺序还比较重要。这题目应该还和以前的系列一样要求先买再卖。

這題是不是可以用merge sort的方法解？因為只需要知道哪些element在左(能買) 哪些在右(能賣)而subarray裡面的順序是可以被排序的
做merge sort的同時用雙指針右邊subarray最大的減去左邊subarray最小的就可以得到當前左右sub array最大的總差價

我不太确定完全理解了题目的意思，我理解的意思大概是每天都可以买或者卖，可以买很多次但是只卖一次。这样理解对吗？
比如说
{1, 2, 3, 4, 1, 5, 4}
买 买 买 买 买 卖 买

这样的最终受益是 4+3+2+1+4 = 14

1. 
   
2. [i]#include <iostream>
   
3. #include <vector>
   
4. using namespace std;
   
5. 
   
6. int maxProfit(vector<int> input)
   
7. {
   
8.     int res = 0;
   
9.     for(int i=input.size()-1, mx=input.back(); i>=0; --i)
   
10.     {
    
11.         mx = max(mx, input[i]);
    
12.         res += mx-input[i];
    
13.     }
    
14.     return res;
    
15. }
    
16. int main()
    
17. {
    
18.     cout << maxProfit({1,2,3,4,1,5,4}) << endl;
    
19. 
    
20.     return 0;
    
21. }[i][i]
    

复制代码

从后往前找最大值，用当前值和最大值的差值作为收益，直到所有的值都访问一次。
这样理解不知道对不对。[/i][/i][/i]