Maximum Subarray Sum

Problem Statement

We are given an array A of size N which consists of both positive and negative integers. We have to write a program to find the Maximum Sum of Subarray.

Note: A subarray is a contiguous part of an Array.

Example

Input: [2,-3,6,-5,4,2]

Output: 7

Explanation: The subarray [6,-5,4,2] is the max sum contiguous subarray with sum 7.

Input: [-2, 5, -2, 3]

Output: 6

Explanation: The Subarray [5, -2, 3] is the max sum contiguous subarray with sum 6.

Constraints

1 <= N <= 10^6
-10^3 <= A[i] <= 10^3

What is a Subarray?

A subarray is a continuous part of the array which can be made by deleting zero or more elements from the beginning or can be made by deleting zero or more elements from the end or both sides.

Example:

Array: [1,3,5,6,2]
Example of some subarrays: [1,3,5], [5,6,2], [3,5,6,2], [1], [1,3,5,6,2]

Approach 1: Brute Force Approach  Using 3 Nested Loops

Algorithm:

• Run a loop from i=0 to i=n-1
• Run a nested loop inside the first loop from j=i to j=n-1
• Run another nested loop inside the second loop from k=i to k=j
• For each subarray calculate the currSum and finally maintain a variable (say maxSum) and each time the innermost loop and we will update the answer by maxSum = max(maxSum,currSum)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int maximumSubarraySum(vector<int> A,int n) {
    int maxSum = INT_MIN;

    for (int i=0;i<=n-1;i++){
        for (int j=i;j<=n-1;j++) {
            int currSum = 0;
            for(int k=i;k<=j;k++){
                currSum += A[k];
            }
            maxSum = max(maxSum,currSum);
    }
}

    return maxSum;
}
int main() {
    vector<int> a = {2,-3,6,-5,4,2};
    int max_sum = maximumSubarraySum(a,a.size());
    cout << max_sum << endl;
    return 0;
}

Java Implementation

class maxsum {
    static void maximumSubarraySum(int A[], int n){
        int maxSum = Integer.MIN_VALUE;

        for (int i=0;i<=n-1;i++){
            for (int j=i;j<=n-1;j++) {
                int currSum = 0;
                for(int k=i;k<=j;k++){
                    currSum += A[k];
                }
                maxSum = Math.max(maxSum,currSum);
            }
        }
        System.out.println(maxSum);
    }
    public static void main(String[] args){
        int a[] = { 2,-3,6,-5,4,2};
        int n = a.length;
        maximumSubarraySum(a, n);
    }
}

Python Implementation

from sys import maxsize
def maximumSubarraySum(A,n):
    maxSum = -100000001;
    for i in range(0,n):
        for j in range(i,n):
            currSum=0
            for k in range(i,j+1):
                currSum += A[k]
            maxSum=max(maxSum,currSum)
 
    print (maxSum)
 
a = [2,-3,6,-5,4,2]
maximumSubarraySum(a,len(a))

Complexity Analysis

Time Complexity Analysis

We can see that we are using 3 Nested Loops

• 1st loop will always run from 0 to n-1 i.e. N times
• In the worst case 2nd loop will run from 0 to n-1 i.e. N times because when i=0, j will run from 0 to n-1.
• In the worst case 3rd loop will run from 0 to n-1 i.e. N times because when i=0 and j=n-1, k will run from 0 to n-1

So the worst-case time complexity of this approach becomes O(N * N * N) i.e. O(N^3)

Space Complexity Analysis

We are only declaring variables that we consider as O(1) space, so its overall space complexity is O(1)

Time complexity: O(N^3)
Space complexity: O(1)

Approach 2: Using two Nested Loops

Algorithm:

• Run a loop from i=0 to i=n-1
• Run a nested loop inside the first loop from j=i to j=n-1
• For each subarray calculate the currSum and finally maintain a variable (say maxSum) and each time the innermost loop and we will update the answer by maxSum = max(maxSum,currSum)

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int maximumSubarraySum(vector<int> A,int n) {
    int maxSum = INT_MIN;

    for (int i=0;i<=n-1;i++){
        int currSum = 0;
        for (int j=i;j<=n-1;j++) {
            currSum += A[j];
            maxSum = max(maxSum,currSum);
        }
    }

    return maxSum;
}
int main() {
    vector<int> a = {2,-3,6,-5,4,2};
    int max_sum = maximumSubarraySum(a,a.size());
    cout << max_sum << endl;
    return 0;
}

Java Implementation

class maxsum {
    static void maximumSubarraySum(int A[], int n){
        int maxSum = Integer.MIN_VALUE;

        for (int i=0;i<=n-1;i++){
            int currSum=0;
            for (int j=i;j<=n-1;j++) {
                currSum+=A[j];
                maxSum = Math.max(maxSum,currSum);
            }
        }
        
        System.out.println(maxSum);
    }
    public static void main(String[] args){
        int a[] = { 2,-3,6,-5,4,2};
        int n = a.length;
        maximumSubarraySum(a, n);
    }
}

Python Implementation

from sys import maxsize
def maximumSubarraySum(A,n):
    maxSum = -100000001;
    for i in range(0,n):
        currSum=0
        for j in range(i,n):
            currSum += A[j]
            maxSum=max(maxSum,currSum)
 
    print (maxSum)
 
a = [2,-3,6,-5,4,2]
maximumSubarraySum(a,len(a))

Complexity Analysis

Time Complexity Analysis

We can see that we are using 2 nested loops

• 1st loop will always run from 0 to n-1 i.e. N times
• In the worst case 2nd loop will run from 0 to n-1 i.e. N times because when i=0, j will run from 0 to n-1.

So the worst-case time complexity of this approach becomes O(N * N) i.e. O(N^2)

Space Complexity Analysis

We are only declaring variables that we consider as O(1) space, so its overall space complexity is O(1)

Time complexity: O(N^2)
Space complexity: O(1)

Approach 3: Using the Divide and Conquer Algorithm

Algorithm:

• Divide the given array into two halves
• Initially, our range is from l=0 to h=n-1
• At each step divide the array using m = (l+h)/2, where m is the middle index and now divide the array into two halves, one from l to m and another from m+1 to h
• Calculate the following 3 values
  1. Maximum Subarray Sum of the left half (By making a recursive call)
  2. Maximum Subarray Sum of the right half (By making a recursive call)
  3. Maximum Subarray Sum such that this subarray crosses the middle point of the array
• Return the maximum of the above calculated 3 values

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int maxSumCrossingMiddle(vector<int> A, int l, int m, int h){
    int curr_sum = 0;
    int sum_of_left = INT_MIN;
    for (int i=m;i>=l;i--) {
        curr_sum+=A[i];
        sum_of_left = max(sum_of_left,curr_sum);
    }
 
    curr_sum = 0;
    int sum_of_right = INT_MIN;
    for (int i=m+1;i<=h;i++) {
        curr_sum+=A[i];
        sum_of_right = max(sum_of_right,curr_sum);
    }
 
    return max({sum_of_left + sum_of_right, sum_of_left, sum_of_right});
}

int maximumSubarraySum(vector<int> A,int l,int h) {
    if (l == h)
        return A[l];
 
    int m = (l + h) / 2;
 
    return max({maximumSubarraySum(A,l,m),
                maximumSubarraySum(A, m + 1, h),
                maxSumCrossingMiddle(A, l, m, h)});
}
int main() {
    vector<int> a = {2,-3,6,-5,4,2};
    int max_sum = maximumSubarraySum(a,0,a.size()-1);
    cout << max_sum << endl;
    return 0;
}

Java Implementation

import java.util.*;
 
class maxsum {
    static int maxSumCrossingMiddle(int a[], int l, int m,
                              int h){
        int curr_sum = 0;
        int sum_of_left = Integer.MIN_VALUE;
        for (int i = m; i >= l; i--) {
            curr_sum +=a[i];
            if (curr_sum > sum_of_left)
                sum_of_left = curr_sum;
        }
        curr_sum = 0;
        int sum_of_right = Integer.MIN_VALUE;
        for (int i = m + 1; i <= h; i++) {
            curr_sum += a[i];
            if (curr_sum > sum_of_right)
                sum_of_right = curr_sum;
        }
        return Math.max(sum_of_left + sum_of_right,
                        Math.max(sum_of_left, sum_of_right));
    }
    static int maximumSubarraySum(int a[], int l, int h)
    {
        if (l == h)
            return a[l];
        int m = (l + h) / 2;
        return Math.max(
            Math.max(maximumSubarraySum(a, l, m),
                     maximumSubarraySum(a, m + 1, h)),
            maxSumCrossingMiddle(a,l,m,h));
    }
 
    public static void main(String[] args)
    {
        int a[] = {2,-3,6,-5,4,2};
        int n = a.length;
        int max_sum = maximumSubarraySum(a,0,5);
        System.out.println(max_sum);
    }
}

Python Implementation

def maxSumCrossingMiddle(a, l, m, h):
    curr_sum = 0
    sum_of_left = -999999
    for i in range(m, l-1, -1):
        curr_sum = curr_sum + a[i]
        if (curr_sum > sum_of_left):
            sum_of_left = curr_sum
            
    curr_sum = 0
    sum_of_right = -999999
    for i in range(m + 1, h + 1):
        curr_sum = curr_sum + a[i]
        if (curr_sum > sum_of_right):
            sum_of_right = curr_sum
            
    return max(sum_of_left + sum_of_right, sum_of_left, sum_of_right)
def maximumSubarraySum(a, l, h):
    if (l == h):
        return a[l]
    m = (l + h) // 2
    return max(maximumSubarraySum(a, l, m),
               maximumSubarraySum(a, m+1, h),
               maxSumCrossingMiddle(a, l, m, h))
a = [2,-3,6,-5,4,2]
n = len(a)
 
max_sum = maximumSubarraySum(a, 0, n-1)
print(max_sum)

Complexity Analysis

Time Complexity Analysis

maximumSubarraySum() is a recursive function in which we are dividing the array into 2 equal parts, and we are calling the maxSumCrossingMiddle() function each time we divide the array, so the Time Complexity is as follows:

• Each time maximumSubarraySum() is divided into 2 equal parts, so the time complexity of dividing the array into two parts, until its size becomes 0 is O(NlogN)
• In the function maxSumCrossingMiddle(), first, i will run from m to l, then i will run from m+1 to h, so in the worst case i can run from 0 to n-1
• So in maxSumCrossingMiddle() the Time Complexity will becon O(N+N) which is equivalent to O(N)

So the worst-case time complexity of this approach becomes O(N * LogN) i.e. O(NLogN)

Space Complexity Analysis

We are only declaring variables that we consider as O(1) space, so its overall space complexity is O(1)

Time complexity: O(N*LogN)
Space complexity: O(1)

Approach 4: Using Kadane’s Algorithm (Dynamic Programming)

Kadane’s Algorithm is a dynamic programming algorithm that can efficiently calculate the maximum subarray sum

Algorithm:

• Initialize a variable named max_till_now=0
• Initialize another variable max_ending_here=0
• Follow the below steps at each index from i=0 to i=n-1
  1. max_ending_here = max_ending_here + A[i]
  2. if(max_ending_here>max_till now)
     max_till_now = max_ending_here
  3. if(max_ending_here<0)
     max_ending_here=0
• Return the variable max_till_now

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

int maximumSubarraySum(vector<int> A, int n)
{
    int max_till_now = 0, max_ending_here = 0;
 
    for (int i=0;i<n;i++)
    {
        max_ending_here = max_ending_here + A[i];
        if (max_ending_here > max_till_now)
            max_till_now = max_ending_here;
 
        if (max_ending_here < 0)
            max_ending_here = 0;
    }
    return max_till_now;
}
 
int main() {
    vector<int> a = {-2,3,-1,2};
    int max_sum = maximumSubarraySum(a,a.size());
    cout << max_sum << endl;
    return 0;
}

Java Implementation

class myClass
{
    static int maximumSubarraySum(int a[],int n)
    {
        int max_till_now = Integer.MIN_VALUE, max_ending_here = 0;
 
        for (int i = 0; i < n; i++)
        {
            max_ending_here = max_ending_here + a[i];
            if (max_till_now < max_ending_here)
                max_till_now = max_ending_here;
            if (max_ending_here < 0)
                max_ending_here = 0;
        }
        return max_till_now;
    }
    public static void main (String[] args)
    {
        int [] a = {-2,3,-1,2};
        System.out.println(maximumSubarraySum(a,4));
    }
}

Python Implementation

def maximumSubarraySum(a,n):
      
    max_till_now = -1000000000
    max_ending_here = 0
      
    for i in range(0, n):
        max_ending_here = max_ending_here + a[i]
        if (max_till_now < max_ending_here):
            max_till_now = max_ending_here
 
        if max_ending_here < 0:
            max_ending_here = 0  
    return max_till_now
  
a = [-2,3,-1,2]
print (maximumSubarraySum(a,len(a)))

Complexity Analysis

Time Complexity Analysis

We can see that we are using only 1 loop in this approach.

• The loop will always run from 0 to n-1 i.e. N times

So the worst-case time complexity of this approach becomes O(N)

Space Complexity Analysis

We are only declaring variables that we consider as O(1) space, so its overall space complexity is O(1)

Time complexity: O(N) Space complexity: O(1)

Explanation

Conclusion

In this quick tutorial, we have discussed 4 different methods to find the Maximum Subarray Sum.

• Method 1: Brute force approach using 3 nested loops | Time Commplexity : O(N^3)
• Method 2: Using 2 nested loops | Time Commplexity : O(N^2)
• Method 1: Using Divide and Conquer algorithm | Time Commplexity : O(NLogN)
• Method 1: Kadane’s Algorithm (Dynamic Programming) | Time Commplexity : O(N)
• We have reduced the Time Complexity from O(N^3) to all the way O(N)