最大子数组和

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

子数组

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

示例 1：

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

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

使用动态规划，f[i]表示以i结尾的最大连续子数组和

显然f[i]=max(f[i-1]+nums[i],nums[i])。因为f[i]必须要以i做结尾，所以必须包含nums[i]，f[i]就是f[i-1]+nums[i]和nums[i]中较大的那一个

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int[] f = new int[n];
        int max = nums[0];
        f[0] = nums[0];
        for (int i = 1; i < n; i++) {
            f[i] = Math.max(f[i - 1] + nums[i], nums[i]);
            max = Math.max(max, f[i]);
        }
        return max;
    }
}

由于每一次循环都只用到了f[i]和f[i-1]，所以空间复杂度还可以优化

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int f =nums[0];
        int max = f;
        for(int i = 1;i<n;i++){
            f = Math.max(f+nums[i],nums[i]);
            max = Math.max(f,max);
        }
        return max;
    }
}