53.Maximum Subarray

Posted on | In

Divide And Conquer, Easy

Question

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.

My Answer

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
38
39
40
41
42
43
44
class Solution {
    public int maxSubArray(int[] nums) {
        return findMaxSubarray(nums, 0, nums.length-1);
    }
    public int findMaxCrossingSubArray(int[] nums, int low, int mid, int high){                                 
        int left_sum = Integer.MIN_VALUE;
        int sum1 = 0;
        int max_left=mid, max_right=mid; //just to record
        for(int i=mid;i>=low;i--){
            sum1 = sum1+nums[i];
            if(sum1>left_sum){
                left_sum = sum1;
                max_left = i;
            }
        }
        int right_sum = Integer.MIN_VALUE;
        int sum2 = 0;
        for(int j=mid+1;j<=high;j++){
            sum2 = sum2+nums[j];
            if(sum2>right_sum){
                right_sum = sum2;
                max_right = j;
            }
        }
        return left_sum+right_sum;
    }
    
    public int findMaxSubarray(int[] nums, int low, int high){
        if(high==low)
            return nums[low];
        else{
            int mid = (high+low)/2;
            int left_sum = findMaxSubarray(nums, low, mid);
            int right_sum = findMaxSubarray(nums, mid+1, high);
            int cross_sum = findMaxCrossingSubArray(nums, low, mid, high);
            
            if(left_sum>=right_sum && left_sum>=cross_sum)
                return left_sum;
            if(right_sum>=left_sum && right_sum>=cross_sum)
                return right_sum;
            else return cross_sum;
        }
    }
}

Running time: O(nlogn), 17ms

Simpler Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxSubArray(int[] nums) {
        int max = Integer.MIN_VALUE, sum = 0;
        for (int i = 0; i < nums.length; i++) {
            if (sum < 0) 
                sum = nums[i];
            else 
                sum += nums[i];
            if (sum > max)
                max = sum;
        }
        return max;
    }
}

Running: O(n), 16ms