53.最大子数组和
给你一个整数数组 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
提示:
- 1 ≤ n u m s . l e n g t h ≤ 1 0 5 1 \leq nums.length \leq 10^5 1≤nums.length≤105
- − 1 0 4 ≤ n u m s [ i ] ≤ 1 0 4 -10^4 \leq nums[i] \leq 10^4 −104≤nums[i]≤104
进阶: 如果你已经实现复杂度为 O(n)
的解法,尝试使用更为精妙的 分治法 求解。
解法一(贪心)
思路分析:
- 首先对于求最大和问题,考虑使用贪心算法来求解
- 思考局部的贪心策略;即对于连续子数组,应该从正数开始作为起始点,因为从负数开始的话,一定会使子数组元素和变小;即使用
count
来统计最大和,当最大和小于0时,则重新更新子数组的起始点,因为count < 0
再添加新的数组元素,总和肯定比新的数组元素更小 - 所以局部贪心为:对子数组求连续和,当连续后为负数时,重新计算连续和,此时变相更新子数组的起始点;而对于子数组的终止位置,则不需要特意寻找,因为可以使用一个变量
result
时刻记录出现的最大和的值,在连续和变化到负数时,result
已经记录了最大连续和 - 因此由局部最优,并时刻记录出现的更大的连续和,可以得到全局最优
实现代码如下:
class Solution {
public int maxSubArray(int[] nums) {
int result = Integer.MIN_VALUE;
int count = 0;
for (int num : nums) {
count += num;
if (count > result) // 时刻更新最大和
result = count;
if (count < 0)
count = 0; // 当连续子数组和小于0时 重置连续和为0
}
return result;
}
}
提交结果如下:
解答成功:
执行耗时:1 ms,击败了100.00% 的Java用户
内存消耗:55.6 MB,击败了84.42% 的Java用户
复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( 1 ) O(1) O(1)