Engineer bro!

Fri Oct 08 2021 (2 months ago)

Engineer by mistake!

I am a software engineer by passion

# 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;
}

max-sumarray