leetcode解题报告(12):Maximum Subarray
描述
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
分析
这道题一开始没什么思路,看了下网上的解答
https://discuss.leetcode.com/topic/6413/dp-solution-some-thoughts
应该是个动态规划(DP)问题,不过说实话我对DP问题还真没什么想法。。。
但是看了下代码,秒懂(看来就算是DP问题,也是DP中的弱智)。
这道题其实很简单,就是我们每取得一个元素,就把它累加,然后和累加前的值做比较,如果比累加前的值大,就取累加后的值,否则就取累加前的值(好像叫局部最优解)。举个例子:
数组A=[1,2,3,-1,1]
当前最大值为6时(即遍历了前三个元素),下一元素为-1,累加后的值(sum)为5,小于6,则最大值(ans)还是6。再累加下一元素,发现累加后sum为6(5+1),因此不变。
但是还要考虑负数的情况:
数组B=[-2,-1,-3,3,2,1]
可以想象一下,如果是一连串的负数,那么每次累加后会变成更小的负数,那还不如不加,更一般的说:当累加后的值sum<0时,那就把sum置为0.
比如对于上面的数组B,一开始sum的值为0(初始值),累加一次后sum的值为-2,比较一次后ans更新为-2.当进入新的一轮循环时,发现sum<0,就把sum置为0,再让sum和新的元素相加,sum变为-1,比较后ans更新为-1.这样,ans就能保证保存的是更大的负数。当遍历到3时,sum经过累加后就为正数了,这时候就回到了数组A的情况。
代码如下:
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN;
int sum = 0;
for(int i = 0; i != nums.size(); ++i){
if(sum < 0) sum = 0;
sum += nums[i];
ans = max(sum,ans);
}
return ans;
}
};
最新文章
- CentOS 6 下安装Python 3
- UI 响应者链
- STL 源代码剖析 算法 stl_numeric.h -- copy
- ECshop lib_base.php on line 1241 错误解决方法
- redhat+11g+rac 安装数据库软件时只有一个节点可选
- HTML5须知十件事
- FFmpeg源代码简单分析:avformat_close_input()
- 20175320 2018-2019-2 《Java程序设计》第7周学习总结
- 更好用的excel国际化多语言导出
- springboot 没有跳转到指定页面
- synchronized(四)
- [转]文件后缀与Mime类型对照表
- Spring boot --- Spring Oauth(一)
- 树莓3B+_teamviewer_install
- 利用arpspoof探取账户密码
- java.lang.IncompatibleClassChangeError: Implementing class
- Spring Boot启动过程(三)
- phpstrom设置php环境
- Android 从上层到底层-----kernel层
- [OS] 死锁相关知识点以及银行家算法详解