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

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 -

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