Coding

Leetcode Maximum subarray solution

5
(2)

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

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 <= 105
  • -104 <= nums[i] <= 104

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

The way you approach this problem was by first reading it and by seeing Maximum Subarray description. Whenever you find in the problem statement something like maximum, minimum, etc., then that problem can be thought as optimization problem. So dynamic programming thought process can be applied.

But first I initially tried to solve it using simple brute force algorithm. Using two for loops, find sum of all sub arrays and then return maximum of those sums.

public int maxSubArray1(int[] nums) {
        // find all subarrays
        // find max subarray
        int maxSum = Integer.MIN_VALUE;
        for (int i=0; i<nums.length; i++) {
            int sum = 0;
            for (int j=i; j<nums.length; j++) {
                sum = sum + nums[j];
                if (maxSum<sum) maxSum = sum;
            }
        }
        return maxSum;
        
    }

It looked simple to implement. But the time complexity is O(n*n), so will definitely not be acceptable in an interview. The interview feedback will be – The candidate was unable to provide optimized solution. 🙂

Then I tried solving the problem using Dynamic Programming/Optimization. I spent some time but could not think of the right sub-problem which could help solve the super-problem. Then I reviewed the greatest source of truth – The Internet. 🙂

Below is the right sub problem that I could find.

maxSubArray[i] – It is the maximum sum of contiguous elements of an array where nums[i] must be included.

Below is how you can derive maxSubArray[i] from maxSubArray[i-1].

maxSubArray[i] = maxSubArray[i-1]>0 ? maxSubArray[i-1] + nums[i] : nums[i];

Once you understand this, solving the problem now looks simple and is now a O(n) solution.

 public int maxSubArray(int[] nums) {
        if (nums.length == 1) return nums[0];
        
        int max = Integer.MIN_VALUE;
        int maxSubArray[] = new int[nums.length];
        maxSubArray[0] = nums[0];
        for (int i=0; i<nums.length; i++) {
            
            maxSubArray[i] = i>0 && maxSubArray[i-1]>0 ? maxSubArray[i-1] + nums[i] :        nums[i];
            max = Math.max(max, maxSubArray[i]);
        }
        return max;
    }

Lessons learnt by solving this problem.

  • If you see in problem statement things like maximum, minimum, average, etc, it could be an optimization problem and dynamic programming and divide and conquer techniques could be handy solving these problems.
  • Spend your time in finding the right sub-problem which can be useful in solving the super problem. Once you are able to find and formulate the right sub-problem, your problem is 90% solved.

How useful was this post?

Click on a star to rate it!

Average rating 5 / 5. Vote count: 2

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?