53. Maximum Subarray

,

DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int maxSubArray(int[] nums) {
        // 定义 dp[i] 为以 nums[i] 结尾的连续子数组的最大和
        int[] dp = new int[nums.length];
        dp[0] = nums[0];

        int maxSum = dp[0];
        for (int i = 1; i < nums.length; i++) {
            if (dp[i - 1] > 0) { // 注意此处比较的是 dp[i - 1] 是否大于 0 而不是 nums[i]，因为根据 dp 定义 nums[i] 是必须添加的
                dp[i] = dp[i - 1] + nums[i];
            } else {
                dp[i] = nums[i];
            }

            maxSum = Math.max(maxSum, dp[i]);
        }

        return maxSum;
    }
}

Divide and Conquer

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
class Solution {
    public int maxSubArray(int[] nums) {
        return maxSubArray(nums, 0, nums.length - 1);
    }

    private int maxSubArray(int[] nums, int left, int right) {
        if (left == right) {
            // 不能再拆分，直接返回
            return nums[left];
        }

        // 此时 left 一定小于 right
        int mid = (left + right) >>> 1;
        return max(maxSubArray(nums, left, mid), maxSubArray(nums, mid + 1, right), maxSum(nums, left, mid, right));
    }

    private int max(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    private int maxSum(int[] nums, int left, int mid, int right) {
        int sum = 0, leftMaxSum = Integer.MIN_VALUE, rightMaxSum = Integer.MIN_VALUE;
        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            leftMaxSum = Math.max(leftMaxSum, sum);
        }

        sum = 0;
        for (int i = mid + 1; i <= right; i++) {
            sum += nums[i];
            rightMaxSum = Math.max(rightMaxSum, sum);
        }

        return leftMaxSum + rightMaxSum;
    }
}

References

53. Maximum Subarray
剑指 Offer 42. 连续子数组的最大和
动态规划设计：最大子数组