Kadane's Approach

#algorithms #codenewbie #programming #career

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