Maximum Sum Contiguous Subarray - LeetCode

The problem is taken from 53. Maximum Subarray.

Brute force approach

For each element in the array we need to find all possible contiguous subarray to the right of it.

Code -

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        int max_sum = INT_MIN; // minimum value of an integer variable

       // find all contiguous subarray starting at index 'i'
       for(int i=0; i<n; i++) {
            int sum=0;
            for(int j=i; j<n; j++) {
                sum += nums[j];
                if(sum>max_sum)
                    max_sum = sum;
            }
        }

        return max_sum;
    }
};

Note - But this is not very efficient. As there is a nested loop. Which makes the time complexity to become O(n^2).

Divide and Conquer method

See the below example briefly we will talk about it later in this article. There are three possibilities to find the required subarray-

  1. Either it falls in left half
  2. Or it falls in right half
  3. Or it overlaps on left and right half of the array, as in the below example

IMG20211204144237.jpg

Pseudo code -

func maxSubArray(A, l, r) 
    #base case
    if l == r: 
         return A[l]

    mid = l + (r - l)/2 # same as (l+r)/2, prev. one prev integer overflow

    RSS = maxSubArray(A, l, mid) # max. sum in left subarray
    LSS = maxSubArray(A, mid+1, r) # max. sum in right subarray
    CSS = maxCrossSubArray(A, l, mid, r) # max. sum in overlapping subarray

    return max(RSS, LSS, CSS)

maxCrossSubArray() -

Let's see what is function do. We use this function to find the overlapping subarray. The approach is - Start from mid index and go to left one element by another and keep adding them and have a tracker for maximum value(say, max_left_sum). Go till extreme left for the respective subarray.

Similarly, Start from mid index and go to right one element by another and keep adding them and have a tracker for maximum value(say, max_right_sum). Go till extreme right for the respective subarray.

Finally, return the value max_left_sum + max_right_sum.

Pseudo code -

func maxCrossSubArray(A, l, mid, r) 
    max_left_sum = max_right_sum = -10^9

    sum=0
    # traverse left 
    For i=mid to l:
         sum = sum + A[i]
         if max_left_sum < sum:
               max_left_sum = sum

    sum=0
    # traverse left 
    For i=mid+1 to r:
         sum = sum + A[i]
         if max_right_sum < sum:
               max_right_sum = sum

    return max_left_sum + max_right_sum

Code -

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        return maxSubArray(nums, 0, n-1);
    }
private:
    int maxSubArray(vector<int>& nums, int l, int r) {
        if(l==r)
            return nums[l];

        int mid = l + (r - l)/2;

        int LSS = maxSubArray(nums, l, mid);
        int RSS = maxSubArray(nums, mid+1, r);
        int CSS = maxCrossSubArray(nums, l, mid, r);

        return max({LSS, RSS, CSS});
    }

    int maxCrossSubArray(vector<int>& nums, int l, int mid, int r) {
        int max_left_sum = INT_MIN;
        int max_right_sum = INT_MIN;

        for(int i = mid, sum=0; i>=l; i--) {
            sum += nums[i];
            if(max_left_sum < sum) 
                max_left_sum = sum; // store max. left subarray sum
        }

        for(int i = mid+1, sum=0; i<=r; i++) {
            sum += nums[i];
            if(max_right_sum < sum) 
                max_right_sum = sum; // store max. left subarray sum
        }

        return max_left_sum + max_right_sum;
    }
};

Complexity -

Time complexity - O(n log(n))