鱼C论坛

 找回密码
 立即注册
查看: 1641|回复: 1

[技术交流] C++刷leetcode(121. 买卖股票的最佳时机)【动态规划】

[复制链接]
发表于 2020-4-20 12:22:50 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
题目描述:
  1. 给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

  2. 如果你最多只允许完成一笔交易(即买入和卖出一支股票一次),设计一个算法来计算你所能获取的最大利润。

  3. 注意:你不能在买入股票前卖出股票。

  4.  

  5. 示例 1:

  6. 输入: [7,1,5,3,6,4]
  7. 输出: 5
  8. 解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。
  9.      注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格;同时,你不能在买入前卖出股票。
  10. 示例 2:

  11. 输入: [7,6,4,3,1]
  12. 输出: 0
  13. 解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

  14. 来源:力扣(LeetCode)
  15. 链接:https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
  16. 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码


  1. int maxProfit(vector<int>& prices) {
  2.         int len = prices.size();
  3.         if(len < 2) return 0;
  4.         int dp[len][2];
  5.         dp[0][0] = 0;
  6.         dp[0][1] = -prices[0];
  7.         for(int i = 1; i < len; i++){
  8.             dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i]);
  9.             dp[i][1] = max(dp[i-1][1], -prices[i]);
  10.         }
  11.         return  dp[len-1][0];
  12.     }
复制代码



参考链接:https://leetcode-cn.com/problems ... hai-fen-si-xiang-b/

本帖被以下淘专辑推荐:

小甲鱼最新课程 -> https://ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2020-4-20 12:24:55 | 显示全部楼层
动态规划的题就是需要细细品
小甲鱼最新课程 -> https://ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2025-7-6 20:31

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表