Kadence’s Algorithm: Largest Sum Contiguous Subarray

What is the largest sum contiguous subarray?

A subarray is a continuous part of an array. It can be a single element of an array or some fraction of the array. The largest sum contiguous subarray means a subarray that has the maximum sum value.

For example, an array is {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Its sub arrays can be: {-10,5,1,6} or {5,1,6} or {2,7,3, -5} etc. But {5,1,6,3} cannot be a subarray because they are not maintaining the sequences.

If you notice, among all the subarrays, following highlighted subarray (5,1,6) has the maximum summation value:

The sum of the subarray {5,1,6} = 11, is the maximum sum in all possible combinations of subarray of the above array. So, for the above array, the maximum subarray is {5,1,6}.

Kadence’s Algorithm: Largest Sum Contiguous Subarray

Simple approach to solving the largest sum contiguous subarray

The simple way to solve this problem is to use two loops to find all the subarrays, calculate the sum, and then find its maximum value.

Here’s the flowchart for the simple approach to finding the largest sum contiguous sub-array. This is a brute force approach, as we’re going through all possible subarrays.

Here are the simple steps to do this.

Step 1) Initialize the max_sum with minimum integer value and assign variables “begin”, and “end” with zero.

Step 2) Let i and j are the index of the array, where “j” is greater than equal to “i”. It represents the beginning index of the subarray, and “j” represents the ending index of the subarray.

Step 3) “Current_sum” will hold the sum of the subarray. After calculating the current sum, check if current_sum is greater than the max_sum.

Step 4) If current_sum is greater, Then replace the max_sum with the current sum.

Step 5) Check if “j” reaches the end of the array or not. If “j” reaches the end of the array, Then increment “i” and change the current_sum value to 0.

Step 6) Perform all these steps, Until “i” reaches the end of the array.

Step 7) At the end of these two loops, The max_sum will hold the largest subarray sum.

Pseudo Code for Simple approach

  function maximumSubarraySum():
    input: array
  for all possible subArray from array:
    calculate sum of each sub array
    store the maximum subArray
  return the maximum sum

C++ Implementation of Simple Approach

#include <stdio.h>
#include <iostream>
using namespace std;
void maximumSubarraySum(int array[], int n) {
  int max_sum = -1e9;
  int begin = 0;
  int end = 0;
  for (int i = 0; i < n; i++) {
    int current_sum = 0;
    for (int j = i; j < n; j++) {
      current_sum += array[j];
      if (max_sum < current_sum) {
        max_sum = current_sum;
        begin = i;
        end = j;
      }
    }
  }
  cout << "largest sum is " << max_sum << endl;
  cout << "largest sum contiguous subarray: ";
  for (int i = begin; i <= end; i++) {
    cout << array[i] << "\t";
  }
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  maximumSubarraySum(array, sizeof(array) / sizeof(array[0]));
}

Output:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Python Implementation of simple approach

def maximumSubarraySum(numbers):
max_sum,begin,end = -1e9, 0 , 0
  for i in range(len(numbers)):
    current_sum=0
  for j in range(i,len(numbers)):
    current_sum+=numbers[j]
  if max_sum<current_sum:
    max_sum=current_sum
  begin,end=i,j
    print("largest sum is ",max_sum)
    print("largest sum contiguous subarray: ",end="")
  for i in range(begin,end+1):
    print(numbers[i],end='\t')
    numbers = [-10,5,1,6,-9,2,-7,3,-5]
    maximumSubarraySum(numbers)

Output:

largest sum is 12
largest sum contiguous subarray: 5      1       6

Kadane’s Algorithm to find the largest sum contiguous subarray

Kadane’s Algorithm is a kind of “Dynamic Programming” method. Here we’ll use one loop instead of two loops. General implementation of Kadane’s Algorithm only works for positive number arrays.

We only need two variables to find the largest sum contiguous subarray. Here’s the flowchart for Kadane’s Algorithm:

Here are the steps for Kadane’s Algorithm:

Step 1) Create two variables, current_sum, and max_sum.

“Current_sum” will keep the value of the maximum sum that ends in a specific array index, while “max_sum” will store the maximum summation value so far.

Step 2) We will add the value with the current_sum for each array element. Then we’ll check two conditions below:

• If current_sum is less than the current element, then the current_sum value will be the current element.
• If max_sum is less than current_sum, then max_sum will be current_sum.

Step 3) Performing the previous step for the entire array, we will have the largest sum contiguous subarray in the “max_sum” variable.

Example of Kadane’s Algorithm

We’ll demonstrate Kadanes’s Algorithm with a small-sized array and discuss every step of finding the largest sum contiguous subarray.

Let’s assume the given array is like the following:

Here’re the steps of Kadane’s Algorithm:

Step 1) Create two variables, current_sum and max_sum. Assign INT_MIN to the max_sum and zero to the current_sum. (Here, INT_MIN means the minimum integer number).

Step 2) At index 0, the value is 4. So, the current_sum = 0 + 4 or 4. Here current_sum is larger than the max_sum, the max_sum will be 4.

Step 3) At index 1, the value is -2. So, the current_sum = 4 + (-2) or 2.

This time the current_sum is less than the max_sum. As a result, the value of max_sum will not be updated.

Step 4) The next value is 1. If we add this with the current_sum, then the current_sum will be 3. Still, the max_sum is greater than the current_sum. So, the max_sum will not be updated.

Step 5) At index 3, the value is three. We’ll update the value by incrementing the current_sum by 3. So, the current_sum will be 6.

In this case, the max_sum is smaller than the current_sum. So, max_sum will be updated with the value of current_sum.

Step 6) For the last element of the array, we’ve -1. If we add this with the current_sum, the current_sum will be 5, which is smaller than the max_sum. So, the max_sum will remain 6.

As we reached the end of the array, the algorithm ends here. Now, “max_sum” contains the maximum sum subarray. Which is 5. The subarray is {4,-2,1,3}.

Pseudo Code for Kadane’s Algorithm

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each elements in array:
        add the element with current_sum
        if current_sum is greater than the maximum_sum
            then maximum_sum = current_sum
        if current_sum is less than the element
            then current_sum = element
    return the value of maximum_sum

C++Implementation of Kadane’s Algorithm

#include < iostream >
using namespace std;
void kadane(int array[], int n) {
  int current_sum = 0;
  int max_sum = -1e9;
  // -1e9 means -10000000
  for (int i = 0; i < n; i++) {
    current_sum += array[i];
    if (max_sum < current_sum) {
      max_sum = current_sum;
    }
    if (current_sum < array[i]) {
      current_sum = array[i];
    }
  }
  cout << "largest sum is " << max_sum << endl;
}
int main() {
  int array[] = {-10, 5, 1, 6, -9, 2, -7, 3, -5};
  kadane(array, sizeof(array) / sizeof(array[0]));
}

Output:

largest sum is 12

Python Implementation of Kadane’s Algorithm

def kadane(numbers):
  current_sum = 0
  max_sum = -1e9
for i in range(len(numbers)):
  current_sum += numbers[i]
if max_sum < current_sum:
  max_sum = current_sum
if current_sum<numbers[i]:
  current_sum = numbers[i]
  print("largest sum is ",max_sum)
  kadane([-10,5,1,6,-9,2,-7,3,-5])

Output:

largest sum is 12

Complexity Analysis for Largest Sum Contiguous Subarray

The simple approach uses two loops. That method calculates all possible subarray sums to find the largest one. It’s a brute force approach. Each loop runs until the end of the array.

If an array has a total of N elements, then using two loops, we will go through N² elements. As a result, the time complexity for a simple approach to find the largest sum contiguous subarray will be O(N2). Here, “O” means the complexity function.

On the other hand, Kadane’s Algorithm is the Dynamic Programming method to find the maximum contiguous sum subarray. If you follow the example or the code, you’ll see that we are using only one loop.

As a result, if the input array has a size of N, then the time complexity of Kadane’s Algorithm will be O(N). This is faster than the simple approach. For example, an array containing 100 elements. The simple approach will take 100*100 or 10,000 CPU time. But the Kadane’s Algorithm will take only 100 CPU time.