Leetcode: Maximum Subarray

This is part of a series of Leetcode and other curated solution explanations (index).
If you liked this solution or found it useful, please like this post.

Leetcode Problem #53 (Easy): Maximum Subarray

53. Maximum Subarray

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

A subarray is a contiguous part of an array.

Example 1:

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

Example 2:

Input: nums = [1]
Output: 1

Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23

Constraints:

1 <= nums.length <= 3 * 104
-105 <= nums[i] <= 105

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.

Solution

This problem can be complex and simple according to how you approach it.

1. Can we find out the pattern to find the max sum possible using a sub-array, say we have a list like 1, 2, 3, 4
   the max sum possible would be 10 right ?

2. So can we say that starting from index 0

   • max sum upto index 0 = 1
   • max sum upto index 2 = 3
   • max sum upto index 3 = 6
   • max sum upto index 4 = 10

let's add some fun then!

now the list is 1, -2, 3, 4

• max sum upto index 0 = 1
• max sum upto index 2 = previous MaxSum or current Value +previous MaxSum? = 1
• max sum upto index 3 = 4
• max sum upto index 4 = 8

so, we can see that even if we summed all the digits, the values comes out to be 8.

let's go for the worse case
-2, 1, -3, 4, -1, 2, 1, -5, 4

• max sum upto index 0 = -2 // by default first digit is max
• max sum upto index 1 = -2 vs 1+-2 = -1 wait, this doesn't look right, if we have a positive number already, why do we have max sum = -1 ok, lets add another layer of check, max = max(num[i], num[i-1]+num[i], maxSum)
  • max sum upto index 1 = -2 vs 1+-2 vs 1 = 1!
• max sum upto index 2 = 1 vs -3 vs -3 = 1
• max sum upto index 3 = 1 vs 4-3 vs 4 = 4
• max sum upto index 4 = 4 vs -1+4 vs -1 = 4
• max sum upto index 5 = 4 vs 2-1 vs 2 = 4 - wait again no! a series of 4, -1, 2 is ok, we can't just take the last two values, we need a concept of localSum. So now localMaxSum = nums[i] + Math.max(0, localMaxSum);
  • max sum upto index 1 = 4 vs -1+2+4 vs 2 = 5!
• max sum upto index 6 = 5 vs 5+1 vs 1 = 6
• max sum upto index 7 = 6 vs 6-5 vs -5 = 6
• max sum upto index 8 = 6 vs 6-5+4 vs 4 = 6

Implementation

  public static int maxSubArray(int[] nums) {

        if (nums == null || nums.length == 0) {
            return 0;
        }

        int maxSum = nums[0];
        int localMaxSum = nums[0];

        for (int i = 1, numsLength = nums.length; i < numsLength; i++) {
            localMaxSum = nums[i] + Math.max(0, localMaxSum);
            maxSum = Math.max(maxSum, localMaxSum);
        }

        return maxSum;
    }
}

Analysis