Largest Sum Contiguous Subarray (Kadane’s Algorithm)

Given an array arr[] of size N. The task is to find the sum of the contiguous subarray within a arr[] with the largest sum. 

The idea of Kadane’s algorithm is to maintain a variable max_ending_here that stores the maximum sum contiguous subarray ending at current index and a variable max_so_far stores the maximum sum of contiguous subarray found so far, Everytime there is a positive-sum value in max_ending_here compare it with max_so_far and update max_so_far if it is greater than max_so_far.

So the main Intuition behind Kadane’s algorithm is, 

– the subarray with negative sum is discarded (by assigning max_ending_here = 0 in code).

– we carry subarray till it gives positive sum.

Pseudocode:

Initialize:
    max_so_far = INT_MIN
    max_ending_here = 0

Loop for each element of the array

  (a) max_ending_here = max_ending_here + a[i]
  (b) if(max_so_far < max_ending_here)
            max_so_far = max_ending_here
  (c) if(max_ending_here < 0)
            max_ending_here = 0
return max_so_far

Illustration:

    Lets take the example: {-2, -3, 4, -1, -2, 1, 5, -3}
    max_so_far = INT_MIN
    max_ending_here = 0

    for i=0,  a[0] =  -2
    max_ending_here = max_ending_here + (-2)
    Set max_ending_here = 0 because max_ending_here < 0
    and set max_so_far = -2

    for i=1,  a[1] =  -3
    max_ending_here = max_ending_here + (-3)
    Since max_ending_here = -3 and max_so_far = -2, max_so_far will remain -2
    Set max_ending_here = 0 because max_ending_here < 0

    for i=2,  a[2] =  4
    max_ending_here = max_ending_here + (4)
    max_ending_here = 4
    max_so_far is updated to 4 because max_ending_here greater 
    than max_so_far which was -2 till now

    for i=3,  a[3] =  -1
    max_ending_here = max_ending_here + (-1)
    max_ending_here = 3

    for i=4,  a[4] =  -2
    max_ending_here = max_ending_here + (-2)
    max_ending_here = 1

    for i=5,  a[5] =  1
    max_ending_here = max_ending_here + (1)
    max_ending_here = 2

    for i=6,  a[6] =  5
    max_ending_here = max_ending_here + (5)
    max_ending_here = 7
    max_so_far is updated to 7 because max_ending_here is 
    greater than max_so_far

    for i=7,  a[7] =  -3
    max_ending_here = max_ending_here + (-3)
    max_ending_here = 4

Follow the below steps to Implement the idea:

• Initialize the variables max_so_far = INT_MIN and max_ending_here = 0
• Run a for loop from 0 to N-1 and for each index i: 
  • Add the arr[i] to max_ending_here.
  • If  max_so_far is less than max_ending_here then update max_so_far  to max_ending_here.
  • If max_ending_here < 0 then update max_ending_here = 0
• Return max_so_far

Below is the Implementation of the above approach.

Maximum contiguous sum is 7

Time Complexity: O(N)
Auxiliary Space: O(1)

Print the Largest Sum Contiguous Subarray 

To print the subarray with the maximum sum the idea is to maintain start index of maximum_sum_ending_here at current index so that whenever maximum_sum_so_far is updated with maximum_sum_ending_here then start index and end index of subarray can be updated with start and current index.

Follow the below steps to implement the idea:

• Initialize the variables s, start, and end with 0 and max_so_far = INT_MIN and max_ending_here = 0
• Run a for loop from 0 to N-1 and for each index i: 
  • Add the arr[i] to max_ending_here.
  • If max_so_far is less than max_ending_here then update max_so_far to max_ending_here and update start to s and end to i .
  • If max_ending_here < 0 then update max_ending_here = 0 and s with i+1.
• Print values from index start to end.

Below is the Implementation of above approach:

Maximum contiguous sum is 7
Starting index 2
Ending index 6

Time Complexity: O(n)
Auxiliary Space: O(1)

Practice Problem: 

Given an array of integers (possibly some elements negative), write a C program to find out the *maximum product* possible by multiplying ‘n’ consecutive integers in the array where n ≤ ARRAY_SIZE. Also, print the starting point of the maximum product subarray.

Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.