53. 最大子序和
难度简单 2926
给定一个整数数组 nums
,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例 1:
输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。
class Solution {
public int maxSubArray(int[] nums) {
int pre = 0, maxAns = nums[0];
for (int x : nums) {
pre = Math.max(pre + x, x);
maxAns = Math.max(maxAns, pre);
}
return maxAns;
// 作者:LeetCode-Solution
// 链接:https://leetcode-cn.com/problems/maximum-subarray/solution/zui-da-zi-xu-he-by-leetcode-solution/
}
}
public int maxSubArray(int[] nums) {
int pre=0;//改为 Integer.MIN_VALUE; 就报错//0 第一次对pre 结果无影响
int max=Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++){
pre =Math.max(pre+nums[i],nums[i]);
max =Math.max(max,pre);
}
return max;
}
解析:我们用
f(i) 代表以第 i 个数结尾的「连续子数组的最大和」,那么很显然我们要求的答案就是:
0≤i≤n−1 max{f(i)}
因此我们只需要求出每个位置的 f(i),然后返回 求出 f 数组中的最大值即可。那么我们如何求 f(i) 呢 ?
我们可以考虑 nums[i] 单独成为一段还是加入 f(i−1) 对应的那一段,这取决于 nums[i] 和 f(i−1)+nums[i]
的大小,我们希望获得一个比较大的,于是可以写出这样的动态规划转移方程:
f(i)=max{f(i−1)+nums[i],nums[i]}