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]}