Leetcode(53) Maximum Subarray

发表于 | 更新于 | 分类于

Description

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Example:

1
2
3
Input: [-2,1,-3,4,-1,2,1,-5,4],
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.

Follow up:

If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

解法

先写写O(n)的算法，动态规划的思想，对于当前元素，和最大有两种情况，要么是以它开始的序列和最大，要么是将它加入之前的序列。即dp[i] = max(nums[i],dp[i-1]+nums[i]). dp代表以当前元素结尾的数组的和的最大值。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] > dp[i - 1] + nums[i]) {
                dp[i] = nums[i];
            } else {
                dp[i] = dp[i - 1] + nums[i];
            }
            if (res < dp[i]) {
                res = dp[i];
            }
        }
        return res;
    }
}

下面来看O(logn)的算法，分治法：

一个子串的最大和是其左子串最大和、右子串最大和、包含中间数的最大和这三者的最大和。根据这种思路分治，关键是合并这一步，即计算包含中间那个数的最大和。这里顺带提一下终止条件，会出现start>=end主要是因为传入的参数是mid-1和mid+1,导致可能大于的情况发生。

具体代码如下：

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

    int helper(int[] nums, int start, int end) {
        if (start >= end) {
            return nums[start];
        }
        int mid = (start + end) / 2;
        int leftmax = helper(nums, start, mid - 1);
        int rightmax = helper(nums, mid + 1, end);
        int middlemax = nums[mid];
        int sum = nums[mid];
        for (int i = mid - 1; i >= start; i--) {
            sum += nums[i];
            middlemax = middlemax > sum ? middlemax : sum;
        }
        sum = middlemax;
        for (int i = mid + 1; i <= end; i++) {
            sum += nums[i];
            middlemax = middlemax > sum ? middlemax : sum;
        }
        return Math.max(leftmax, Math.max(rightmax, middlemax));
    }
}