LeetCode - Maximum Subarray

Problem description

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:

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.

Analysis

Basically idea is to use sum from index 0 to index j minus sum from index 0 to index i to get the sum of subarray from i to j.

Here’s the code:

class Solution {
    public int maxSubArray(int[] nums) {
        int min = 0, max = Integer.MIN_VALUE;
        int sum = 0;
        int res = Integer.MIN_VALUE;
       
        int max_value = Integer.MIN_VALUE;
        
        if (nums.length == 1){
            return nums[0];
        }
        
        for (int i:nums){
            max_value = Math.max(max_value, i);
            sum += i;
            if (sum < min){
                min = sum;
                max = Integer.MIN_VALUE;
            }
            
            if (sum > max){
                max = sum;
            }
            
            if (max != Integer.MIN_VALUE){
                res = Math.max(res, max - min);                
            }
        }
        
        if (max_value < 0){
            return max_value;
        }
        
        return res;
    }
}

However, this solution is not straightforward and has many edge cases to deal with.

There’s a greedy solution from LeetCode, basic idea is to use the max current sum, use the nums[i] and sum from previous subarray + nums[i].

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int currSum = nums[0], maxSum = nums[0];

        for(int i = 1; i < n; ++i) {
        currSum = Math.max(nums[i], currSum + nums[i]);
        maxSum = Math.max(maxSum, currSum);
        }
        return maxSum;
    }
}

Also, LeetCode provide a divide and conquer method, which runs in O(NlogN), but the thought is great. The basic idea is to use something like merge sort.

here’s the code:

class Solution {
  public int crossSum(int[] nums, int left, int right, int p) {
    if (left == right) return nums[left];

    int leftSubsum = Integer.MIN_VALUE;
    int currSum = 0;
    for(int i = p; i > left - 1; --i) {
      currSum += nums[i];
      leftSubsum = Math.max(leftSubsum, currSum);
    }

    int rightSubsum = Integer.MIN_VALUE;
    currSum = 0;
    for(int i = p + 1; i < right + 1; ++i) {
      currSum += nums[i];
      rightSubsum = Math.max(rightSubsum, currSum);
    }

    return leftSubsum + rightSubsum;
  }

  public int helper(int[] nums, int left, int right) {
    if (left == right) return nums[left];

    int p = (left + right) / 2;

    int leftSum = helper(nums, left, p);
    int rightSum = helper(nums, p + 1, right);
    int crossSum = crossSum(nums, left, right, p);

    return Math.max(Math.max(leftSum, rightSum), crossSum);
  }

  public int maxSubArray(int[] nums) {
    return helper(nums, 0, nums.length - 1);
  }
}

What to improve

• main idea of this question is that if we have a smaller sum we should restart the subarray. Instead of using min, max to restart, a better idea is to just use the max between current sum and nums[i].

• the edge case, only one item.

• the merge sort like problem, if we found a problem that can be divide and conquer, use that.