Vineeth's Blog
Maximum Subarray Sum

Maximum Subarray Sum

M.Vineeth's photo
M.Vineeth
·

6 min read

Given an array of integers, our motive is to find the sum of contiguous subarray of numbers having the largest sum.

The subarrays are continuous ie unlike subsequences or subsets, elements can't be skipped in between. If all the elements are positive, then the subarray would be the entire array itself. However, the problem gets interesting when some negative elements are there in between.

There are a lot of ways to solve for Maximum Subarray sum, the most common ones being :

  • Bruteforce
  • Divide and Conquer
  • Dynamic Programming

Brute force algorithm follows O(n^3) time complexity and a little modification for calculating the sum of successive elements could reduce the time complexity down to O(n^2) and an additional space complexity of O(n).

Divide and Conquer approach is very systematic and provides the solution in O(nlogn) which is a huge improvement over the bruteforce solutions.

Kadane's algorithm solves the problem in O(n) time complexity with no extra space complexity.

1. Naive Bruteforce Approach

#include <iostream>
#include <climits>
using namespace std;

// O(n^3) naive approach
void allSubarrays(int arr[], int n) {
    pair<int, int> ind;
    int max_sum = INT_MIN, cur_sum = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            cur_sum = 0;
            //Elements of subarray(i, j)
            for(int k = i; k <= j; k++) {
                cur_sum += arr[k];
            }
            if(cur_sum > max_sum) {
                max_sum = cur_sum;
                ind = make_pair(i, j);
            }
        }
    }
    cout << "Max sum : " << max_sum << endl;
    cout << "Subarray : ";
    for(int i = ind.first; i <= ind.second; i++) {
        cout << arr[i] << " ";
    }

}

int main() {
    // given an array, find a subarray which has the maximum sum.
    // note : The subarrays are continuous.
    // if all the elements are positive, then the subarray would be the entire array itself.
    // the problem gets interesting when some negative elements are there in between.
    int n;
    cout << "Enter the size of the array : ";
    cin >> n;
    int arr[n];
    cout << "Enter the elements of the array : ";
    for(int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    cout << "All subarrays of the given array : \n";
    allSubarrays(arr, n);

    return 0;
}

Here, the inner-most loop is used to establish the sum of elements starting from index 'i' till index 'j'. A pair object has been used to store the indexes marking the starting and the ending index of the maximum sum subarray.

One can easily note that this particular inner loop is redundant as the sum of the subarray from index 'i' to 'j' can be calculated cumulatively instead of creating a loop to calculate it independently in every iteration.

2. A little modification in Bruteforce 

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

// this function returns a pointer to the array.
vector<int> cumulativeSum(int arr[], int n) {
    vector<int> csum;
    csum.push_back(arr[0]);
    for(int i = 1; i < n; i++) {
        csum.push_back(csum[i - 1] + arr[i]);
    }
    return csum;
}

// O(n^2) cumulative sum approach
void allSubarrays(int arr[], int n) {
    pair<int, int> ind;
    vector<int> csum = cumulativeSum(arr, n);
    int max_sum = INT_MIN, cur_sum = 0;
    for(int i = 0; i < n; i++) {
        for(int j = i; j < n; j++) {
            //sum of elements of subarray(i, j)
            cur_sum = csum[j] - csum[i] + arr[i];

            if(cur_sum > max_sum) {
                max_sum = cur_sum;
                ind = make_pair(i, j);
            }
        }
    }
    cout << "Max sum : " << max_sum << endl;
    cout << "Subarray : ";
    for(int i = ind.first; i <= ind.second; i++) {
        cout << arr[i] << " ";
    }

}

With the help of cur_sum = csum[j] - csum[i] + arr[i], we could compute the sum in constant time ie O(1) but increasing the space complexity to O(n).

3. Divide and Conquer Approach along with index

Approach:
1) Divide the given array in two halves
2) Return the maximum of following three
a) Maximum subarray sum in left half (Make a recursive call)
b) Maximum subarray sum in right half (Make a recursive call)
c) Maximum subarray sum such that the subarray crosses the midpoint

#include <iostream>
#include <climits>
using namespace std;

typedef pair<int, pair<int, int>> pp;

// this time we will return the subarray too along with the max sum.

// utility function to find max of 3 numbers
pp max(pp p1, pp p2, pp p3) {
    if(p1.first > p2. first and p1.first > p3.first) {
        return p1;
    }
    else if(p2.first > p1.first and p2.first > p3.first) {
        return p2;
    }
    else {
        return p3;
    }
}
// crossing sum through mid.
pp crossingsum(int arr[], int start, int mid, int end) {
    // elements to the left of mid, start the sum from mid towards the left.
    pp p;
    int sum = 0;
    int left_sum = INT_MIN;
    for(int i = mid; i >= start; i--) {
        sum += arr[i];
        if(sum > left_sum) {
            left_sum = sum;
            p.second.first = i;
        } 
    }

    // elements to the right of mid, start the sum from mid + 1 towards the right.
    sum = 0;
    int right_sum = INT_MIN;
    for(int i = mid + 1; i <= end; i++) {
        sum += arr[i];
        if(sum > right_sum) {
            right_sum = sum;
            p.second.second = i;
        }
    }
    p.first = left_sum + right_sum;
    return p;

}
pp subarraysumDivandConquer(int arr[], int start, int end) {
    // base case, only 1 element is there.
    if(start == end) {
        pp base;
        base.first = arr[start];
        base.second.first = start;
        base.second.second = end;
        return base;
    }

    pp p1, p2, p3;
    // p1.first --> sum
    // p1.second.first --> left index of the required subarray
    // p1.second.second --> right index of the required subarray
    int mid = (start + end) / 2;
    p1 = subarraysumDivandConquer(arr, start, mid);
    p2 = subarraysumDivandConquer(arr, mid + 1, end);
    p3 = crossingsum(arr, start, mid, end);

    return(max(p1, p2, p3)); 
}

Here i have used a pair object typedef pair<int, pair<int, int>> pp where the first term stores the sum, the second term stores the starting index and the last term stores the ending index of the maximum subarray sum.

4. Dynamic Programming

int kadane_dp(int *arr, int n) {
    int dp[n];
    memset(dp, 0, sizeof(dp));
    dp[n - 1] = arr[n - 1];
    for(int i = n - 2; i >= 0; i--) {
        dp[i] = max(arr[i], arr[i] + dp[i + 1]);
    }
    return *max_element(dp, dp + n);
}

Here, we fill the dp array from right to left ie. following the top to bottom approach. dp[i] indicates the maximum sum of all the subarrays starting from index 'i'.

5. Kadane's Algorithm

void kadane(int arr[], int n) {
    int cur_sum = 0, max_sum = INT_MIN;
    for(int i = 0; i < n; i++) {
        cur_sum += arr[i];
        max_sum = max(cur_sum, max_sum);
        if(cur_sum < 0) {
            cur_sum = 0;
        }
    }

    cout << "Max subarray sum : " << max_sum << endl;
}

The simple intuition behind this algorithm is as follows

Starting from the array if you encounter positive elements, embrace them. If by taking negative elements, some positivity is left then sustain the negativity and keep moving ahead hoping that you might gain higher positivity in the long run. Contrary to this, by taking negativity if you become negative. Then you need to drop the negativity and start afresh, continuing the traversal from first positive intake.
I have included all major approaches to solve this problem. If you have some different interesting approach, do comment down.
Hope you liked this article. Feel free to share your thoughts and connect with me on linkedin and github

Competitive programmingC++