发布于2019-12-07 17:14 阅读(848) 评论(0) 点赞(29) 收藏(2)
最近做了两道子序列问题,分别是
53、最大子序列和和152、乘积最大子序列
他们解决的办法大致相同,都是经过一次遍历保存一个遍历到当前数字的最大值,然后保留一个当前增益或但当前成绩,于是放到一起做一个总结。
53、最大子序列和(来自leetcode题解)
动态规划的是首先对数组进行遍历,当前最大连续子序列和为 sum,结果为 ans
如果 sum > 0,则说明 sum 对结果有增益效果,则 sum 保留并加上当前遍历数字
如果 sum <= 0,则说明 sum 对结果无增益效果,需要舍弃,则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小,将最大值置为ans,遍历结束返回结果
时间复杂度:O(n)
- class Solution {
- public int maxSubArray(int[] nums) {
- int ans = nums[0];
- int sum = 0;
- for(int num: nums) {
- if(sum > 0) {
- sum += num;
- } else {
- sum = num;
- }
- ans = Math.max(ans, sum);
- }
- return ans;
- }
- }
-
152、乘积最大子序列
这道题值只是跟上一道略有不同。
令imax为当前最大值,则当前最大值为 imax = max(imax * nums[i], nums[i])
由于存在负数,那么会导致最大的变最小的,最小的变最大的。因此还需要维护当前最小值imin,imin = min(imin * nums[i], nums[i])
当负数出现时则imax与imin进行交换再进行下一步计算
时间复杂度:O(n)
- class Solution:
- def maxProduct(self, nums: List[int]) -> int:
- maxx,imax,imin=float('-inf'), 1, 1
- for num in nums:
- if num<0:
- imax, imin = imin, imax
- imax = max(imax*num,num)
- imin = min(imin*num,num)
- maxx=max(maxx,imax)
- print(maxx,imax,imin)
- return maxx
作者:短发越来越短
链接:https://www.pythonheidong.com/blog/article/170165/b786068a225250509ca4/
来源:python黑洞网
任何形式的转载都请注明出处,如有侵权 一经发现 必将追究其法律责任
昵称:
评论内容:(最多支持255个字符)
---无人问津也好,技不如人也罢,你都要试着安静下来,去做自己该做的事,而不是让内心的烦躁、焦虑,坏掉你本来就不多的热情和定力
Copyright © 2018-2021 python黑洞网 All Rights Reserved 版权所有,并保留所有权利。 京ICP备18063182号-1
投诉与举报,广告合作请联系vgs_info@163.com或QQ3083709327
免责声明:网站文章均由用户上传,仅供读者学习交流使用,禁止用做商业用途。若文章涉及色情,反动,侵权等违法信息,请向我们举报,一经核实我们会立即删除!