贪心算法:区间问题只是记录自己的刷题过程,答案参考过多种题解。
如有错误感谢指正!
参考:① LeetCode 101: A LeetCode Grinding Guide (C++ Version) 作者:高畅 Chang Gao
② 代码随想录 (programmercarl.com) 作者:程序员Carl
题目来源:题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台 (leetcode-cn.com)
自己的思路:选一个低的买入,在选个高的卖,在选一个低的买入.....循环反复。
结果:太麻烦了,且具体实现有很多bug。
// 实现不了,有数组越界的空指针异常 while (i < prices.length) { if (start >= prices[i]) { start = prices[i++]; } else { int end = prices[i]; while (i < prices.length) { ······
-
最终利润可以分解为每天收益情况的总和。假如第0天买入,第3天卖出,那么利润为:prices[3] - prices[0]。相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
-
把利润分解为每天为单位的维度,而不是整体区间去考虑!那么根据prices可以得到每天的利润序列:(prices[i] - prices[i - 1]).....(prices[1] - prices[0])。
-
第一天没有利润,至少要第二天才会有利润,所以利润的序列比股票序列少一天。
-
从图中可以发现,其实我们需要收集每天的正利润就可以,收集正利润的区间,就是股票买卖的区间,而我们只需要关注最终利润,不需要记录区间。那么只收集正利润就是贪心所贪的地方!
-
局部最优:收集每天的正利润;全局最优:求得最大利润。
public int maxProfit(int[] prices) { int sum = 0; for (int i = 1; i < prices.length; i++) { sum += Math.max(prices[i] - prices[i - 1], 0); //只收集每天的正利润 } return sum; }
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)