Leetcode — 53. Maximum Subarray

The link to the problem: https://leetcode.com/problems/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.

Example 
Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Since this contiguous array [4,-1,2,1] has the maximum sum 6.

Thoughts:

So according to the problem, we need to find our contiguous “target array” in the given array.
The easier way is using brute force. We use two pointers i and j to represent the start and end position of our “target array”.
We will update the maximum sum once we found the current sum (i.e., temp) is larger than the original.

The code will be like below —

public int maxSubArray(int[] nums) {
        int n = nums.length; 
        int max = nums[0];
        for(int i=0;i<n;i++)
        {
            int temp = 0;
            for(int j=i;j<n;j++)
            {
                temp += nums[j];
                max = Math.max(max,temp);
            }
        }
        return max;
    }

The time complexity of the above code is O(n²) since we try every combination of our target array to find the maximum sum.

Let’s think if there’s any way that we can solve the problem in O(n) 💭

If we go through the process of the above code, we are actually wasting some time adding sums repeatedly. (For example, for arrays like [a,b,c,d], we will add c+d 3 times, since we will add them in when start positions are a, b, and c.) We might also be wasting time adding the sums that we already know won’t be our maximum sum.

We need an extra variable “temp” to control the maximum sum we can get till position i.

• When temp is negative, we will just give up all the sum we aggregated so far (i.e., we will let nums[i] be our temp maximum sum till position i). Since no matter nums[i] is positive or negative, nums[i] will always bigger than a negative number add on it.
• If temp is positive, we will simply add nums[i] on it. We don’t care even if nums[i] is negative because it is possible that i+1 has a larger number. Our goal is to extend the “target array” and get a larger sum. We will just keep extending the array as long as if there’s a chance to increase the sum.

public int maxSubArray(int[] nums) {
        int n = nums.length; 
        int max = nums[0];
        int temp = nums[0];
        for(int i=1;i<n;i++)
        {
            if(temp<0)
                temp = nums[i];
            else
                temp += nums[i];
            max = Math.max(max,temp);
        }
        return max;
    }

Follow-Up question —

Although we already found how we solve the problem in O(n), there’s one follow-up question here asking us if we can solve the problem using divide and conquer. i.e., time complexity will be O(nlgn)

If we want to use divide and conquer to solve the problem, it means that we can divide the problem into smaller problems until we can’t divide it anymore. In each subproblem, we should return the maximum sum in the given starting point and the ending point of the array.

There are three possible parts that the maximum sum appears between the given started position i and ending position j:
1. first half — the maximum sum between i and before the midpoint
2. second half— the maximum sum between the point right after the midpoint and j
3. middle — the maximum sum from midpoint to the left to midpoint to the right

public int maxSubArray(int[] nums) {
        return helper(nums,0,nums.length-1);
    }
    public int helper(int[] nums,int i,int j){
        if(i==j)
            return nums[i];
        if(i>j)
            return Integer.MIN_VALUE;
        int mid= i+(j-i)/2;
        int leftSum = helper(nums,i,mid-1);
        int rightSum = helper(nums,mid+1,j);
        
        int crossSum = nums[mid]; 
        //from mid to left
        int tempLeft = 0;
        int maxLeft = 0;
        for(int k=mid-1;k>=i;k--)
        {
            tempLeft += nums[k];
            maxLeft = Math.max(maxLeft,tempLeft);
        }
        //from mid to right
        int tempRight = 0;
        int maxRight = 0;
        for(int k=mid+1;k<=j;k++)
        {
            tempRight += nums[k];
            maxRight = Math.max(maxRight,tempRight);
        }
        crossSum += maxLeft+maxRight;
        
        return Math.max(crossSum, Math.max(leftSum,rightSum));
    }