Engineer bro!

Fri Oct 08 2021 (2 years ago)

Engineer by mistake!

I am a software engineer by passion

Max Sum Contiguous Subarray

You are given an array AA and you have to find a continues sub-array of AA which has the largest sum over any other sub-array of AA.

Problem Constraints

1 <= N <= 1e6
-1000 <= A[i] <= 1000

Input Format

The first and only input of the algorithm is an array AA.

Output Format

Return an integer representing the maximum possible sum of the contiguous subarray.

Example Input

Input 1:

 A = [1, 2, 3, 4, -10] 

Input 2:

 A = [-2, 1, -3, 4, -1, 2, 1, -5, 4] 

Example Output

Output 1:
1010
Output 2:
66

Example Explanation

  • Explanation 1: The subarray [1,2,3,4][1, 2, 3, 4] has the maximum possible sum of 10.

  • Explanation 2: The subarray [4,āˆ’1,2,1][4,-1,2,1] has the maximum possible sum of 66.

Function Description

int maxSubArray(const vector<int> &A) {
    // return max sum
}

Method 1 - Brute force way

The brute force way is to go through each sub-array of AA then calculate its sum and compare it with the sum of the other subarrays of AA. Keep the maximum sum overall.

int maxSubArray(const vector<int> &A) {
    // initially initialize maximum as minimum
    int maxSum = INT_MIN;

    for(int i=0; i<A.size(); i++){
        for(int j=i; j<A.size(); j++){
            // for every sub array calculate the sub array sum
            // them compare it with maxSum and update maxSum as maximum of maxSum and curSum
            int curSum = 0;

            for(int k=i; k<= j; k++){
                curSum += A[k];
            }
            
            // update maxSum
            maxSum=max(maxSum,curSum);
        }
    }
    return maxSum;
}

Complexity

  • Time - O(n)O(n)

  • Space - O(1)O(1)

nn is size of array AA

Method 2 - removing the unnecessary loop - O(n2)O(n^2)

Before understanding that how to optimize the code, I would like to explain to you that how we are processing the sub-arrays.

Consider the array [1,2,3][1,2,3], if we print all the sub-arrays using the above code, then it'll be printed as follows.

1
1, 2
1, 2, 3
2
2, 3
3

You can see that the first loop is considering every index of AA as starting point of a sub-array. Then add an element each time to get a sub-array of size greater than 11 than the previous sub-array.

For example, I have sub-array [1][1] (A[0])(A[0]). To get the next sub-array, just append A[1]A[1] to it. Now, the next sub-array will looks like, [1,2][1,2].

So, instead of iterating over [1,2][1,2] again, we can just use sub-array [1][1] to get the sum of [1,2][1,2] by just adding 22 to sum([1])sum([1]).

This way we can eliminate the third loop and calculate the sum of the sub-array on the fly.

int maxSubArray(const vector<int> &A) {
    // initially initialize maximum as minimum
    int maxSum = INT_MIN;

    for(int i=0; i<A.size(); i++){
        int subArraySum = 0;
        for(int j=i; j<A.size(); j++){
            subArraySum += A[j];
            maxSum = max(maxSum,subArraySum);
        }
    }
    return maxSum;
}

Ā© 2021 dsabyte. All rights reserved