DEV Community

Cover image for Kadane's Approach
Aishanii
Aishanii

Posted on

2 1

Kadane's Approach

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;
    }
Enter fullscreen mode Exit fullscreen mode

Image of Timescale

Timescale – the developer's data platform for modern apps, built on PostgreSQL

Timescale Cloud is PostgreSQL optimized for speed, scale, and performance. Over 3 million IoT, AI, crypto, and dev tool apps are powered by Timescale. Try it free today! No credit card required.

Try free

Top comments (0)