Leetcode-121
2022/1/29 23:10:55
本文主要是介绍Leetcode-121,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
动态规划,不会。
硬着头皮上。
官方的答案确实很厉害;
找历史最低点(),然后计算今天卖得到的收益是多少。
首先是找一个很大的值,假设第一天之前的历史最低点(注意不包括今天)为一个很大的值,这样对第一天而言,它的历史最低点是那个很大的值。
然后从第一天开始遍历,此时我们已经知道了这一天的历史最低价格,就可以计算倘若今天卖出的收益是多少。
计算后,结果肯定是个负值,和我们的初始设置的最大收益0比较,显然是小的,所以我们选择第一天不卖出。
接着,我们算算下一天的历史最低价格。
然后遍历完就可以了。
class Solution { public: int maxProfit(vector<int>& prices) { int minvalue=1e4; int maxprofit=0; for(int i=0;i<prices.size();i++){ maxprofit=max(maxprofit,prices[i]-minvalue); minvalue=min(minvalue,prices[i]); } return maxprofit; } };
按照我自己的方法来(看了一半标准答案):
用一个数组记录(第一天到今天)的最低价格(包括和今天价格的比较);
接着,第一天的最低价格显然就是第一天的价格;
我们开始遍历,从第一天到最后一天,计算每天的最低价格。
再计算假如今天卖出股票的利润,然后与最大利润变量做比较,取最大值。
但我有个疑问,买入和卖出的天不能相同,这个怎么办呢?
class Solution { public: int maxProfit(vector<int>& prices) { vector<int> mindp; mindp.push_back(prices[0]); int maxvalue=0; for(int i=1;i<prices.size();i++) //i必须从1开始。 { mindp.push_back(min(mindp[i-1],prices[i])); maxvalue=max(maxvalue,prices[i]-mindp[i]); } return maxvalue; } };
我自己想的方法:
class Solution { public: int maxProfit(vector<int>& prices) { vector<int> dp; int maxvalue=0; dp.push_back(max((prices[1]-prices[0]),0)); for(int i=1;i<prices.size();i++){ dp.push_back(max(dp[i-1],dp[i-1]+prices[i]-prices[i-1])); maxvalue=max(maxvalue,dp[i]); } return maxvalue; } };
这篇关于Leetcode-121的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升