53. 最大子序和


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++)&#123;
            pre =Math.max(pre+nums[i],nums[i]);
            max =Math.max(max,pre);
        &#125;
        return max;
    &#125;

解析:我们用  
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]}


文章作者:   future
版权声明:   本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 future !
 上一篇
628. 三个数的最大乘积 628. 三个数的最大乘积
628. 三个数的最大乘积class Solution &#123; public int maximumProduct(int[] nums) &#123; Arrays.sort(nums);
2021-02-27 future
下一篇 
704. 二分查找 704. 二分查找
704. 二分查找给定一个  n  个元素有序的(升序)整型数组  nums 和一个目标值  target  ,写一个函数搜索  nums  中的 target,如果目标值存在返回下标,否则返回 -1。 class Solution &am
2021-02-27 future
  目录