## DEV Community π©βπ»π¨βπ» is a community of 968,873 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

Aishanii

Posted on

Most common question for Kadane application is here.

Kadane Algorithm is an iterative DP algorithm which carries out calculation of maximum sum at a position by considering the same at previous position.

So in the above mentioned question we are

• Taking `cur_sum=0` & `max_sum=INT_MIN` as variables

• We iterate over the array and check if

• 1. `cur_sum>max_sum` and then
• 2 `arr[i]>max_sum` and then
• 3 `arr[i]>cur_sum`.
• Once it's done for the whole array, we return `max_sum`.

For the complete code check Arrays/KadaneAlgo.cpp

Here, `max_sum_current` is the cur_sum and `max_ends` is the max_sum.

``````class Solution{
public:

long long maxSubarraySum(int arr[], int n){

long long max_sum_current=arr[0];
long long max_ends=arr[0];

for(int i=1;i<n;i++){
max_sum_current+=arr[i];

if(max_sum_current>max_ends){
max_ends=max_sum_current;

}

if(max_ends<arr[i]) {
max_ends=arr[i];
max_sum_current=arr[i];
}

if(max_sum_current<arr[i]){
max_sum_current=arr[i];
}
}
return  max_ends;
}
``````