题目
给定一个整数数组nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例1
- 输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
- 输出:6
- 解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
示例2
- 输入:nums = [1]
- 输出:1
示例3
输入:nums = [5,4,-1,7,8]
输出:23
思路
暴力解法
- 暴力解法的思路,第一层
for
就是设置起始位置,第二层for
循环遍历数组寻找最大值
JAVA
1 | class Solution{ |
注:此方法的时间复杂度为
O(n^2)
,空间复杂度为O(1)
,一般会超过题目给定的时间限制,提示超时错误
贪心算法
所谓贪心算法,就是在子序和为负数时,直接舍弃当前count
,对其count
进行重新赋值0
的操作,因为负数只会拉低综合,这便是局部最优。
从代码角度上来讲:遍历nums
,从头开始用count
累积,如果count
一旦加上nums[i]
变为负数,那么就应该从nums[i+1]
开始从0
累积count
了,因为已经变为负数的count
,只会拖累总和。
- 注:这相当于是暴力解法中的不断调整最大子序和区间的起始位置。
代码实现
JAVA
1 | class Solution { |
v1.5.1