LC.P53[最大子数组和]

方法一：动态规划

f[i]表示以 $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, ans = nums[0];
        int[] f = new int[n];
        f[0] = nums[0];
        for (int i = 1; i < n; ++i) {
            if (f[i - 1] > 0) f[i] = f[i - 1] + nums[i];
            else f[i] = nums[i];
            ans = Math.max(ans, f[i]);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

方法二：优化空间

由于 $f[i]$ 只与 $f[i - 1]$ 有关系，因此可以只用一个变量 $f$ 来维护对于当前 $f[i]$ 的值是多少

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = nums[0], f = nums[0];
        for (int i = 1; i < nums.length; ++i) {
            f = Math.max(f, 0) + nums[i];
            ans = Math.max(ans, f);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$

方法三：前缀和

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxSubArray(int[] nums) {
        int ans = Integer.MIN_VALUE, minPreSum = 0, preSum = 0;
        for (int x : nums) {
            preSum += x;
            ans = Math.max(ans, preSum - minPreSum);
            minPreSum = Math.min(minPreSum, preSum);
        }
        return ans;
    }
}
  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(1)$