[LeetCode] 53. Maximum Subarray

Posted on | In

Problem

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.

Explanation

  1. We are finding the maximum of a subarray, which means we need to continuosily adding numbers, also we need to return one maximum number, which means we need to have a variable to keep track of the maximum.

  2. While iterating, the sum is keep adding current number. If the sum is less than the current number, we can just drop the sum, and reset the sum to the current number. And we compare the sum with the maximum result.

  3. Finally, return the maximum result.

Solution 1

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxSubArray(int[] nums) {
        int currentMax = nums[0];
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i], currentMax+nums[i]);
            res = Math.max(res, currentMax);
        }
        return res;
    }
}

Explanation 2

  1. We can also use divide and conquer method to solve this problem. First, we divide the array into left half and right half, and find their max sum. We also need to find the max sum for the middle part which is crossing the left half and right half, and we can find it by starting from the middle number and scan left side and scan the right side. Finally, compare these three sums.

Solution 2

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
class Solution {
    public int helper(int[] nums, int left, int right) {
        int sum = 0, leftSum = Integer.MIN_VALUE, rightSum = Integer.MIN_VALUE;
        int mid = (left+right)/2;

        for (int i = mid; i >= left; i--) {
            sum += nums[i];
            if (sum > leftSum) {
                leftSum = sum;
            }
        }
        sum = 0;
        for (int i = mid+1; i <= right; i++) {
            sum += nums[i];
            if (sum > rightSum) {
                rightSum = sum;
            }
        }

        sum = leftSum + rightSum;
        return sum;
    }

    public int maxSubArrayHelper(int nums[], int left, int right) {
        if (left == right) {
            return nums[left];
        }
        int mid = (left+right) / 2;
        return Math.max(Math.max(maxSubArrayHelper(nums, left, mid),
                        maxSubArrayHelper(nums, mid+1, right)),
                        helper(nums, left, right)
                       );
    }
    public int maxSubArray(int[] nums) {
        return maxSubArrayHelper(nums, 0, nums.length-1);
    }
}