题目

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。示例：

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

暴力法

把所有子序列都找出来并求出最大和。利用两个循环，外循环记录开始下标，内循环记录结束下标。不断维护一个最大 sum。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    // T:O(n^2) S:O(1)
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int max = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int cur = 0;
            for (int j = i; j < nums.length; j++) {
                cur += nums[j];
                max = Math.max(max, cur);
            }
        }
        return max;
    }
}

在线处理法

在线处理意味着在每次循环过程中都计算出一个当前最终值。遍历过程中维护一个 cur 用来表示当前的值左边的最大非负数的和。如果 cur 小于 0 意味着舍弃掉，反之就带上。在加上了当前值之后，由于当前值的正负，所以还需要维护一个 max 用来找到最大值。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    // T:O(n) S:O(1)
    public int maxSubArray(int[] nums) {
        int cur = 0, max = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            cur = cur <= 0 ? nums[i] : (cur + nums[i]);
            max = Math.max(max, cur);
        }
        return max;
    }
}

动态规划法

假设函数 f(i) 表示下标从 0 到 i 的子序列最大值。

假设数组为 [-2]，f(0) = -2

假设数组为 [-2, 1]， f(1) = 1

假设数组为 [-2, 1, -3]， f(2) = 1

从上述可以发现。f(1) 可以看成 f(0) + nums[1] 与 nums[1] 比较的较大值；并且 f(2) 也满足这个条件。 那么可以容易得到状态转移方程：f(i) = max(f(i - 1) + nums[i], nums[i])。写出代码就是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    // T:O(n) S:O(n)
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];
        int result = nums[0];
        dp[0] = result;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1] + nums[i], nums[i]);
            result = Math.max(dp[i], result);
        }
        return result;
    }
}