This post is completed by 2 users

  • 1
 Add to List
Medium

198. Kadane's Algorithm - Maximum Subarray Problem

Objective:  The maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers that 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:

The naive solution would be to use two for loops and check every subarray and return the subarray which has the maximum sum.

Time Complexity: O(N2)

Can we reduce it??? Yes, there are multiple solutions that solve this problem in O(N). In this article, we will see a very known algorithm called kadane's Algorithm.

Click here to read about how to solve this problem using Dynamic Programming.
Kadane's Algorithm:

start:
    max_sum = 0
    current_sum = 0

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

Let's walk through this algorithm with one example

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

max_sum = 0
current_sum = 0

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

i=1 and a[1] = 1
current_sum = current_sum + (1) => 0 + 1 => 1
current_sum > 0
max_sum < current_sum is true => max_sum = current_sum
max_sum = 1

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

i=3 and a[3] = 4 current_sum = current_sum + 4 => 0 + 4 => 4
current_sum > 0
max_sum < current_sum is true => max_sum = current_sum
max_sum = 4

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

i=5 and a[5] = 2 current_sum = current_sum + 2 => 3 + 2 => 5
current_sum > 0
max_sum < current_sum is true => max_sum = current_sum
max_sum = 5


i=6 and a[6] = 1
current_sum = current_sum + 1 => 5 + 1 => 6
current_sum > 0
max_sum < current_sum is true => max_sum = current_sum
max_sum = 6

return max_sum = 6

NOTE: The above algorithm works only when there is at least one positive element in the array.

We need to modify the algorithm to work it if all the elements are negative.

start:
    max_sum = a[0]
    current_sum = a[0]

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

return max_sum

Output:

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

Print the Maximum Subarray

To print the maximum subarray we will keep track of start and end index while finding the maximum subarray sum. Have three variables start, end and max_start. Every time current_sum resets to 0, reset the start. and every time we update the max_sum, do end = current index and set max_start= start.

Look the code below for more understanding 

Output:

4 -1 2 1 
Maximum subarray is  6

References:
https://en.wikipedia.org/wiki/Maximum_subarray_problem
http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/

Related Problems: