Kadane’s Algorithm to solve Maximum Subarray Problem

Kadane's Algorithm

Maximum Subarray Problem is a famous problem in dynamic programming. The algorithm we use to solve this problem is known as Kadane’s algorithm. It is a slightly tricky algorithm to understand but don’t you worry. This tutorial we go over the algorithm in an easy to understand manner.

What is the Maximum Subarray Problem?

This problem requires you to find the largest possible sum of a contiguous subarray, within a given one-dimensional array A[1…n] of numbers.

The array will contain negative integers. If the array only contains positive integers then the answer will be the sum of the complete array.

Kadane’s Algorithm

The Kadane’s Algorithm solves this problem by traversing over the entire array and keeping two variables to track the sum so far and overall maximum.

The conditions under which each of the two variables are updated are important.

Let’s look at the algorithm :

  1. Initialize max_so_far = 0
  2. Initialize max_ending_here = 0
  3. Repeat steps 4 to 6 for each element of the array
  4. set max_ending_here = max_ending_here + a[i]
  5. if(max_ending_here < 0) then set max_ending_here = 0
  6. if(max_so_far < max_ending_here) then set max_so_far = max_ending_here
  7. return max_so_far

That’s Kadane’s algorithm in six seven easy steps.

We can summarize the update criteria in two sentences :

When the variable max_ending_here becomes negative, we set it to zero. At each iteration, we check for max_so_far < max_ending_here, if the condition is true then we update max_so_far.

The for loop for steps 4 to 6 will be :

for (int i = 0; i < length; i++) 
        { 
            max_ending_here = max_ending_here + arr[i]; 
            if (max_so_far < max_ending_here) 
                max_so_far = max_ending_here; 
            if (max_ending_here < 0) 
                max_ending_here = 0; 
        } 

Example

Let’s look at an example :

Kadanes Array

The maximum subarray is from i=2 to i=6. The maximum sum is 7.

Kadane’s algorithm Implementation

The complete code for Kadane’s algorithm is as follows, in the code we have printed the values of max_so_far and max_ending_here at each step.

1. Java

package com.JournalDev;

public class Main {
    static int maxSubArraySum(int arr[]) {
// initializing variables 
        int length = arr.length;
        int max_so_far = 0, max_ending_here = 0;

// for loop step 4 to 6
        for (int i = 0; i < length; i++) {
            max_ending_here = max_ending_here + arr[i];
            if (max_so_far < max_ending_here)
                max_so_far = max_ending_here;
            if (max_ending_here < 0)
                max_ending_here = 0;
            System.out.println("For i = "+i);
            System.out.println("Max_ending_here = "+max_ending_here);
            System.out.println("Max_so_far = "+max_so_far);
            System.out.println();
        }
//return max_so_far as the answer 
        return max_so_far;
    }

    public static void main(String[] arg) {
        int [] arr = {-2, -3, 4, -1, -2, 1, 5, -3};
        System.out.println("Maximum sum is " +
                maxSubArraySum(arr));


    }
}

2. C++

#include<iostream> 
#include<climits> 
using namespace std; 
  
int maxSubArraySum(int arr[], int length) 
{ 
// initializing variables 
    int max_so_far = 0, max_ending_here = 0; 
  
// for loop step 4 to 6
    for (int i = 0; i < length; i++) 
    { 
        max_ending_here = max_ending_here + arr[i]; 
        if (max_so_far < max_ending_here) 
            max_so_far = max_ending_here; 
  
        if (max_ending_here < 0) 
            max_ending_here = 0; 

 cout << "For i = " << i; 
cout << "Max_ending_here = " << max_ending_here;
cout << "Max_so_far = " << max_so_far ;


    } 
    return max_so_far; 
} 
  
int main() 
{ 
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3}; 
    int n = sizeof(arr)/sizeof(arr[0]); 
    int max_sum = maxSubArraySum(arr, n); 
    cout << "Maximum contiguous sum is " << max_sum; 
    return 0; 
} 
Output : 

For i = 0
Max_ending_here = 0
Max_so_far = 0

For i = 1
Max_ending_here = 0
Max_so_far = 0

For i = 2
Max_ending_here = 4
Max_so_far = 4

For i = 3
Max_ending_here = 3
Max_so_far = 4

For i = 4
Max_ending_here = 1
Max_so_far = 4

For i = 5
Max_ending_here = 2
Max_so_far = 4

For i = 6
Max_ending_here = 7
Max_so_far = 7

For i = 7
Max_ending_here = 4
Max_so_far = 7

Maximum sum is 7
Kadane Output

Conclusion

This tutorial was about Kadane’s algorithm. If you’re interested in more problems like this, you should check our tutorial on subset sum problem.

Leave a Reply

Your email address will not be published. Required fields are marked *

close
Generic selectors
Exact matches only
Search in title
Search in content
Search in posts
Search in pages