DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’»

DEV Community πŸ‘©β€πŸ’»πŸ‘¨β€πŸ’» is a community of 966,904 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Create account Log in
Cover image for Leetcode: Maximum Subarray
Saurabh Kumar
Saurabh Kumar

Posted on

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Analysis

alt text

Top comments (1)

πŸ‘‹ Hey, my name is Noah and I’m the one who set up this ad. My job is to get you to join DEV, so if you fancy doing me a favor, I’d love for you to create an account.

If you found DEV from searching around, here are a couple of our most popular articles on DEV: