Maximum sum of all subarrays using Kadane’s algorithm in C++

By utkarsh bhadauria

An algorithm to solve the problem of the maximum sum of all subarrays in time complexity O(n).

Problem Statement - 

 

Given an array arr with n elements , we need to find the maximum sum of all subarrays of the array.  A subarray is a continuous part of an array with same or lesser elements. 

 

Example - 

 

Input - 

N = 5 

Arr = {-1, 4, -6, 7, -4}

 

Output -  

7 

 

Algorithmn - 

 

We will traverse the array while simultaneously calculating the cumulative sum upto the i th element of the array and storing it in an variable currsum. If at any point currsum gets negative, we set currsum to 0. We also update a variable maxsum to store the maximum upto the i th iteration of the loop.

 

This algorithm is a major upgrade on the brute force approach as the latter has a time complexity of O(n^3).

 

Code - 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int arr[n];
    for(int i=0;i<n;i++)
    {
        cin>>arr[i];
    }
    int currsum=0;
    int maxsum=INT_MIN;
    for(int i=0;i<n;i++)
    {
        currsum+=arr[i];
        if(currsum<0)
        {
            currsum=0;
        }
        maxsum = max(maxsum,currsum);
    }
    cout<<maxsum;
    return 0;
}