Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

Kadane’s Algorithm — Maximum Subarray Problem

Objec­tive:  The max­i­mum sub­ar­ray prob­lem is the task of find­ing the con­tigu­ous sub­ar­ray within a one-dimensional array of num­bers which has the largest sum.

Example:
int [] A = {−2, 1, −3, 4, −1, 2, 1, −5, 4};
Output: contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

Approach:

Naive solu­tion would be use two for loops and check every sub­ar­ray and return the sub­ar­ray which has the max­i­mum sum.

Time Com­plex­ity: O(N2)

Can we reduce it??? Yes, there are mul­ti­ple solu­tions which solves this prob­lem in O(N). In this arti­cle we will see very known algo­rithm called kadane’s Algorithm.

Click here to read about how to solve this prob­lem using Dynamic Pro­gram­ming.
Kadane’s Algo­rithm:

start:
    max_so_far = 0
    max_ending_here = 0

loop i= 0 to n
  (i) max_ending_here = max_ending_here + a[i]
  (ii) if(max_ending_here < 0)
            max_ending_here = 0
  (iii) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
return max_so_far

Let’s walk through this algo­rithm with one example

int [] A = {−2, 1, −3, 4, −1, 2, 1};

max_so_far = 0
max_ending_here = 0

i=0 and a[0] = -2
max_ending_here = max_ending_here + (-2) = -2
max_ending_here < 0 => max_ending_here = 0

i=1 and a[1] = 1
max_ending_here = max_ending_here + (1) => 0 + 1 => 1
max_ending_here > 0 
max_so_far < max_ending_here is true => max_so_far = max_ending_here
max_so_far = 1

i=2 and a[2] = -3
max_ending_here = max_ending_here + (-3) => 1 -3 = -2
max_ending_here < 0 => max_ending_here = 0
max_so_far < max_ending_here is false so do not update max_so_far. max_so_far = 1

i=3 and a[3] = 4 max_ending_here = max_ending_here + 4 => 0 + 4 => 4
max_ending_here > 0 
max_so_far < max_ending_here is true => max_so_far = max_ending_here
max_so_far = 4

i=4 and a[4] = -1
max_ending_here = max_ending_here + (-1) => 4 - 1 => 3
max_ending_here > 0 
max_so_far < max_ending_here is false max_so_far = 4 

i=5 and a[5] = 2 max_ending_here = max_ending_here + 2 => 3 + 2 => 5
max_ending_here > 0 
max_so_far < max_ending_here is true => max_so_far = max_ending_here
max_so_far = 5


i=6 and a[6] = 1
max_ending_here = max_ending_here + 1 => 5 + 1 => 6
max_ending_here > 0 
max_so_far < max_ending_here is true => max_so_far = max_ending_here
max_so_far = 6

return max_so_far = 6

NOTE: The above algo­rithm works only when there is at least one pos­i­tive ele­ment in the array.

We need to mod­ify the algo­rithm to work it if all the ele­ments are negative.

start:
    max_so_far = a[0]
    max_ending_here = a[0]

loop i= 1 to n
  (i) max_end_here = Max(arrA[i], max_end_here+a[i]);
  (ii) max_so_far = Max(max_so_far,max_end_here);

return max_so_far

Com­plete Code for both algorithms:

Out­put:

Maximum subarray is  10
Maximum Subarray when all elements are negative : -2

 

Ref­er­ences:
https://en.wikipedia.org/wiki/Maximum_subarray_problem

You may also like...