Max Sum Contiguous Subarray

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

Problem Constraints

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

Input Format

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

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:
$10$
Output 2:
$6$

Example Explanation

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

• Explanation 2: The subarray $[4,-1,2,1]$ has the maximum possible sum of $6$.

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 $A$ then calculate its sum and compare it with the sum of the other subarrays of $A$. 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)$

• Space - $O(1)$

$n$ is size of array $A$

Method 2 - removing the unnecessary loop - $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]$, 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 $A$ as starting point of a sub-array. Then add an element each time to get a sub-array of size greater than $1$ than the previous sub-array.

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

So, instead of iterating over $[1,2]$ again, we can just use sub-array $[1]$ to get the sum of $[1,2]$ by just adding $2$ to $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;
}