Fri. Dec 2nd, 2022

Hello Android

All android in one place

Kadane’s Algorithm to solve Maximum Subarray Problem

3 min read

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 :

www.hello-android.com

Leave a Reply

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

Hello android © All rights reserved. | Newsphere by AF themes.