数组Array-53.最大子序和

提示：自己学习用的

文章目录

• 53.最大子序和
• • 1.动态规划
  • 2.贪心法

53.最大子序和

题目描述：给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组 是数组中的一个连续部分。

1.动态规划

-1，2，-3，5，-7，9

需要求出每个位置对应的‘连续子数组的最大和’，再求出这些这些最大和中最大的那个值。

e.g. -1位置上对应的‘连续子数组最大和’为-1.
2位置上对应的‘连续子数组最大和’为2 > -1 + 2

所以

class Solution {
    public int maxSubArray(int[] nums) {
        int sub = 0;
        int result = nums[0];
        for(int n : nums){
            if(sub + n > n){
                sub = sub + n;
            }else{
                sub = n;
            }
            
            if(result < sub){
                result = sub;
            }
        }
        return result;
    }
}

2.贪心法

迭代数组，从左向右一个一个加，记录下最大值，但如果sum<0则将sum归零重新加数。

因为当sum<0时说明加上它之后result只会越来越小，所以要把sum归零后重新开始找子序串。

class Solution {
    public int maxSubArray(int[] nums) {
        int sum = 0;
        int result = nums[0];
        for(int n : nums){
            sum += n;
            if(result < sum)
            {
                result = sum;
            }
            if(sum < 0){
                sum = 0;
            }
        }
        return result;
    }
}