剑指 Offer 42. 连续子数组的最大和

53. 最大子数组和

题目描述

输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为O(n)。

输入输出

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

基本思路

前缀和：每个i的最大和取决于上一个i的最大和

假设当前遍历到位置 i，那么 preSum 就是代表区间 [0, i] 的累加和。

有什么用呢？前缀和是让你可以在O(1)时间内查询出任意连续区间的累加和的。比如有个数组：[1,2,3,4,5]，我现在知道区间 [0, 2] 的区间和是 1+2+3=6 ， [0,4] 的区间和是 1+2+3+4+5=15 ， 那么 [3, 4] 的区间和就可以通过上面两者区间做差得到，是 9

如果我们再拿一个变量记录 preSum 出现过的最小值，那么：preSum - minSum = maxSum，即答案要求的 “连续最大和” 了

动态规划：状态转移方程 f(i) = max{f(i-1)+nums[i], nums[i]}

  1. dp[i]: 表示以 nums[i] 结尾的连续子数组的最大和
  2. 状态转移方程:
    1. 如果dp[i - 1] > 0 dp[i] = dp[i - 1] + nums[i]
    2. 如果dp[i - 1] <= 0 dp[i] = nums[i]
  3. 初始化: dp[0] = nums[0]
  4. 输出 max(dp)

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// 时间复杂度：O(n^2) 无法通过
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE;
		for(int i = 0;i < nums.length;i++){
            int sum = 0;
            for(int j = i;j < nums.length;j++){
                //sum(i,j)=sum(i,j-1)+nums[j]
                sum += nums[j];
                if(sum > max)
                	max = sum;
            }
        }
        return max;
    }
}

// 前缀和 时O(n)空O(1)
class Solution {
    public int maxSubArray(int[] nums) {
        int min = 0;
        int ans = Integer.MIN_VALUE;
        int num = 0;
        for(int i = 0 ; i < nums.length ; i++){
            num += nums[i];
            ans = Math.max(ans , num - min);
            if(num<min){
                min = num;
            }
        }
        return ans;
    }
}

// 动态规划 时O(n)空O(n)
class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        if(len == 0) return 0;
        //dp[i]:指以nums[i]结尾的最大连续子数组和
        int[] dp = new int[len];
        dp[0] = nums[0];
        int res = nums[0];
        for(int i = 1; i < len; i++){
            dp[i] = Math.max(dp[i-1] + nums[i], nums[i]);
            res = Math.max(dp[i], res);
        }
        return res;
    }
}

// 滚动数组优化 时O(n)空O(1)
class Solution {
    public int maxSubArray(int[] nums) {
        int len = nums.length;
        int max = nums[0], ans = max;
        for(int i = 1; i < len; i++){
            max = Math.max(max + nums[i], nums[i]);
            ans = Math.max(max, ans);
        }
        return ans;
    }
}