作者:whisper
链接:https://www.proprogrammar.com/article/907
声明:请尊重原作者的劳动,如需转载请注明出处
输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。
示例1:
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
提示:
1 <= arr.length <= 10^5
-100 <= arr[i] <= 100
难度:简单;标签:分法,动态规划;编程语言:C++
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int sum = 0;
int max = INT_MIN;
for(int i = 0; i < nums.size(); i++)
{
if(sum > 0)
{
sum += nums[i];
}
else
{
sum = nums[i];
}
if(sum > max)
{
max = sum;
}
}
return max;
}
};
只要子数组和小于0,那么丢弃不用,如果子数组和大于0,那么就有可能,这个不好理解,因为子数组和可能会减小,但只要大于0,就是可以的,如
1 2 -2 3,sum为1 3 1 4,虽然中间减小了,但大于0,与后面的连在一起还是可能是最大的,而1 2 -2 1,sum为1 3 1 2,虽然最后的2不是最大,但3也已经算出来了,也是对的
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论