Coders Packet

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 -  


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 - 

using namespace std;
int main()
    int n;
    int arr[n];
    for(int i=0;i<n;i++)
    int currsum=0;
    int maxsum=INT_MIN;
    for(int i=0;i<n;i++)
        maxsum = max(maxsum,currsum);
    return 0;


Download Complete Code


No comments yet

Download Packet

Reviews Report

Submitted by utkarsh bhadauria (utk251199)

Download packets of source code on Coders Packet