糖逗 发表于 2020-4-23 00:06:06

C++刷leetcode（122. 买卖股票的最佳时机 II）【有限制条件的动态规划】

题目描述：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。

注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。

 

示例 1:

输入:
输出: 7
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。
示例 2:

输入:
输出: 4
解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。
     注意你不能在第 1 天和第 2 天接连购买股票，之后再将它们卖出。
     因为这样属于同时参与了多笔交易，你必须在再次购买前出售掉之前的股票。
示例 3:

输入:
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 

提示：

1 <= prices.length <= 3 * 10 ^ 4
0 <= prices <= 10 ^ 4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


int maxProfit(vector<int>& prices) {
      int len = prices.size();
      if(len < 2) return 0;
      int dp;
      dp = 0;
      dp = -prices;
      for(int i = 1 ; i < len ;i++){
            dp = max(dp + prices, dp);
            dp = max(dp, dp - prices);
      }
      return max(dp, dp);      
    }

永恒的蓝色梦想 发表于 2020-4-23 07:00:40

这题正好是之前Python版的每日一题{:10_327:}
不过我觉得这道题还可以写的更简单：如果我们持有股票，那么明天上涨我们肯定赚钱。如果没有持有股票，今天买入明天一样赚钱。所以只要上涨我们就赚钱。
用这个思路写代码，应该可以更快一点？{:10_316:}

糖逗 发表于 2020-4-23 08:11:14

永恒的蓝色梦想 发表于 2020-4-23 07:00
这题正好是之前Python版的每日一题
不过我觉得这道题还可以写的更简单：如果我们持有股票，那么 ...

可以看看我股票的上一个帖子，这道题和上道题一样。这道题和上道题一样有限制，就是卖出前必须有买入。此外，除了买入卖出状态外还有一种既不买入也不卖出的状态。最终这三种状态都归位持有和不持有两种状态。我感觉并不是上涨就一定赚钱，比如1，2，6，我第一天买入第三天卖出要比第一天买入第二天卖出赚的多。不知道你说的是不是这个意思。{:5_91:}

永恒的蓝色梦想 发表于 2020-4-23 08:16:27

糖逗 发表于 2020-4-23 08:11
可以看看我股票的上一个帖子，这道题和上道题一样。这道题和上道题一样有限制，就是卖出前必须有买入。此 ...

比如1，2，6，我第一天买入第三天卖出要比第一天买入第二天卖出赚的多第一天买入第三天卖出就把所有上涨的钱都赚到了

永恒的蓝色梦想 发表于 2020-4-23 08:17:52

糖逗 发表于 2020-4-23 08:11
可以看看我股票的上一个帖子，这道题和上道题一样。这道题和上道题一样有限制，就是卖出前必须有买入。此 ...

如果他会上涨的话，你总有方法把钱赚到。

糖逗 发表于 2020-4-23 08:24:16

永恒的蓝色梦想 发表于 2020-4-23 08:17
如果他会上涨的话，你总有方法把钱赚到。

但这样能保证最大利润吗？{:10_272:}

永恒的蓝色梦想 发表于 2020-4-23 08:28:03

糖逗 发表于 2020-4-23 08:24
但这样能保证最大利润吗？

你既然把能赚的钱都赚到了，还不是最大利润嘛？

糖逗 发表于 2020-4-23 08:31:24

永恒的蓝色梦想 发表于 2020-4-23 08:28
你既然把能赚的钱都赚到了，还不是最大利润嘛？

还是没太明白你的题解，可以写代码看看吗{:10_297:}

永恒的蓝色梦想 发表于 2020-4-23 08:33:42

糖逗 发表于 2020-4-23 08:31
还是没太明白你的题解，可以写代码看看吗

我的题解，方法B

糖逗 发表于 2020-4-23 09:00:22

永恒的蓝色梦想 发表于 2020-4-23 08:33
我的题解，方法B

懂了，是可以今天卖出又同时买入，只要涨价了就可以{:10_279:}
页: [1]
查看完整版本: C++刷leetcode（122. 买卖股票的最佳时机 II）【有限制条件的动态规划】