最大子数组和

发表于 分类于 ， ， 阅读次数：

题目描述

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

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

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-subarray

我的题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxSubArray(int[] nums) {
        int[] sum=new int[nums.length+1];
        int min=0;
        int result=nums[0];
        for(int i=1;i<sum.length;i++)
        {
            sum[i]=sum[i-1]+nums[i-1];
            if(sum[i-1]<min)
            {
                min=sum[i-1];
            }
            result=Math.max(result,sum[i]-min);
            
        }
        return result;

    }
}

本题我的思想主要是用到了前面的前缀和思想,求连续位置的和就可以用通项公式s[m]-s[n],再加上s[i]自身就行，所以再的第一项添零，到这里要求数组s右边减左边的最大值，可以在向右移动过程中固定最左边的最小值来优化求数组s右边减左边的最大值的算法，否则两层for循环暴力是通过不了的。

大神题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0];
        int sum = 0;
        for(int num: nums) {
            if(sum > 0) {
                sum += num;
            } else {
                sum = num;
            }
            ans = Math.max(ans, sum);
        }
        return ans;
    }
}


作者：guanpengchn
链接：https://leetcode.cn/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
来源：力扣（LeetCode）

思路
动态规划的是首先对数组进行遍历，当前最大连续子序列和为 sum，结果为 ans
如果 sum > 0，则说明 sum 对结果有增益效果，则 sum 保留并加上当前遍历数字
如果 sum <= 0，则说明 sum 对结果无增益效果，需要舍弃，则 sum 直接更新为当前遍历数字
每次比较 sum 和 ans的大小，将最大值置为ans，遍历结束返回结果

作者：guanpengchn
链接：https://leetcode.cn/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/
来源：力扣（LeetCode）