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, take the array {-10, 5, 1, 6, -9, 2, -7, 3, -5}. Its subarrays can be {-10, 5, 1, 6}, {5, 1, 6}, or {2, -7, 3, -5}, and so on. However, {5, 1, 6, 3} cannot be a subarray because the elements are not in a contiguous sequence.

If you notice, among all the subarrays, the highlighted subarray {5, 1, 6} has the maximum summation value:

The sum of the subarray {5, 1, 6} is 12, the maximum sum across all possible subarrays of the above array. So, for this array, the maximum sum contiguous subarray is {5, 1, 6}.

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 is the flowchart for the simple approach to finding the largest sum contiguous subarray. This is a brute-force approach, as we go through every possible subarray.

Here are the simple steps to do this.

Step 1) Initialize max_sum with the minimum integer value and set begin and end to zero.

Step 2) Let i and j be array indices where j is greater than or equal to i; i marks the subarray start and j its end.

Step 3) current_sum holds the running sum. After each update, check if current_sum is greater than max_sum.

Step 4) If current_sum is greater, replace max_sum with it.

Step 5) When j reaches the end of the array, increment i and reset current_sum to 0.

Step 6) Repeat until i reaches the end of the array. max_sum then holds the largest subarray sum.

Pseudo Code for Simple Approach

function maximumSubarraySum():
    input: array
    for all possible subArray from array:
        calculate sum of each subarray
        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 Dynamic Programming method that uses a single loop instead of two. It handles arrays with mixed positive and negative numbers, as long as at least one value is non-negative.

We only need two variables to find the largest sum contiguous subarray. Here is the flowchart:

Here are the steps for Kadane’s Algorithm:

Step 1) Create two variables, current_sum and max_sum.

current_sum keeps the maximum sum that ends at a specific array index, while max_sum stores the largest summation value observed so far.

Step 2) Add each array element to current_sum. Then check the two conditions below:

• If current_sum is less than the current element, then current_sum becomes the current element.
• If max_sum is less than current_sum, then max_sum becomes current_sum.

Step 3) After repeating the previous step for the entire array, max_sum holds the largest sum contiguous subarray.

Example of Kadane’s Algorithm

We demonstrate Kadane’s Algorithm on a small array and walk through every step of finding the largest sum contiguous subarray.

Let us assume the given array is like the following:

Here are the steps of Kadane’s Algorithm:

Step 1) Create two variables, current_sum and max_sum. Assign INT_MIN to max_sum and zero to current_sum. Here, INT_MIN represents the minimum integer value.

Step 2) At index 0, the value is 4. So, current_sum = 0 + 4 = 4. Since current_sum is larger than max_sum, max_sum becomes 4.

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

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

Step 4) The next value is 1. Adding it to current_sum gives 3. Since max_sum (4) is still greater than current_sum, max_sum is not updated.

Step 5) At index 3, the value is 3. Incrementing current_sum by 3 gives current_sum = 6.

In this case, max_sum is smaller than current_sum, so max_sum is updated with the value of current_sum.

Step 6) For the last element of the array, we have -1. Adding it to current_sum gives 5, which is smaller than max_sum. So, max_sum remains 6.

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

Pseudo Code for Kadane’s Algorithm

function KadaneAlgorithm():
    input: array
    maximum_sum, current_sum = 0
    for each element 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 -1,000,000,000
    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 to calculate every possible subarray sum and locate the largest one. It is a brute-force approach; each loop runs to the end of the array, giving O(N²) time.

Kadane’s Algorithm uses only one loop, giving O(N) time and O(1) extra space. On an array of 100 elements the simple approach performs 100 × 100 = 10,000 operations, while Kadane’s performs only 100 — a dramatic speed-up for large inputs.

FAQs