Kadane's Algorithm to find Maximum subarray sum

Kadane’s algorithm is a simple and efficient technique used to solve the maximum subarray problem. This problem involves finding the contiguous subarray within a given array that has the maximum sum among all other contiguous subarrays.

Maximum Sum of Contiguous Sub Array

Before proceeding to the actual algorithm, let’s first try to understand what contiguous sub arrays are and what maximum subarray sum is.

A contiguous subarray is a continuous sequence of elements within a larger array. Let’s say we have an array with the following values [2, -3, 4, 1]. Below are all possible contiguous subarrays along with corresponding sums:

[2] -> sum = 2
[2, -3] -> sum = -1
[2, -3, 4] -> sum = 3
[2, -3, 4, 1] -> sum = 4
[-3] -> sum = -3
[-3, 4] -> sum = 1
[-3, 4, 1] -> sum = 2
[4] -> sum = 4
[4, 1] -> sum = 5

Among all these subarrays, the subarray [4, 1] has the maximum sum of 5. So 5 is the maximum subarray sum for the array [2, -3, 4, 1].

There are different techniques to find out the maximum subarray sum for a given array which includes brute force, divide and conquer, dynamic programming etc., but Kadane’s algorithm is efficient and simplest among all other techniques.

Kadane’s Algorithm & Implementation

Kadane’s algorithm works by keeping track of two values: the maximum subarray sum so far, and the maximum subarray sum ending at the current element. The algorithm starts by initializing these two values to the first element of the array.

Then, as it goes through the array, it either adds the current element to maximum subarray ending at the previous element and increments the current subarray sum. Or it starts a new subarray starting from the current element and resets the current subarray sum. It also keeps track of the maximum sum among all the subarray sums computed so far. Below is the implementation of this algorithm:


def find_max_subarray_sum(arr):
  # Initialize the maximum subarray sum so far
  max_so_far = arr[0]
  # Initialize the maximum subarray sum ending at the current element
  max_ending_here = arr[0]

  # Iterate through the array starting from the second element
  for i in range(1, len(arr)):
    # If the current subarray sum is positive, add the current element to it
    if max_ending_here > 0:
      max_ending_here = max_ending_here + arr[i]
    # Otherwise, start a new subarray sum from the current element
    else:
      max_ending_here = arr[i]

    # Update the maximum subarray sum so far
    # If the maximum subarray ending at the current element is greater
    max_so_far = max(max_so_far, max_ending_here)

  # Return the maximum subarray sum so far
  print(f"Maximum Subarray Sum for array {arr} is {max_so_far}")
  return max_so_far

# Example usage
find_max_subarray_sum([2, -3, 4, 1]) # Expected output: 5


#include <stdio.h>
#include <stdlib.h>

int find_max_subarray_sum(int* arr, int size) {
  // Initialize the maximum subarray sum so far
  // And the maximum subarray sum ending at the current element
  int max_so_far = arr[0];
  int max_ending_here = arr[0];

  // Iterate through the array starting from the second element
  for (int i = 1; i < size; i++) {
    // If the current subarray sum is positive, add the current element to it
    if (max_ending_here > 0) {
      max_ending_here = max_ending_here + arr[i];
    }
    // Otherwise, start a new subarray sum from the current element
    else {
      max_ending_here = arr[i];
    }

    // Update the maximum subarray sum so far
    // If the maximum subarray ending at the current element is greater
    if (max_ending_here > max_so_far) {
      max_so_far = max_ending_here;
    }
  }

  // Return the maximum subarray sum so far
  printf("Maximum Subarray Sum for array [2, -3, 4, 1] is %d\n", max_so_far);
  return max_so_far;
}

int main() {
  int arr[] = {2, -3, 4, 1};
  int size = sizeof(arr) / sizeof(arr[0]);
  find_max_subarray_sum(arr, size);
  return 0;
}


#include <iostream>
#include <algorithm>

int findMaxSubarraySum(int arr[], int n) {
  // Initialize the maximum subarray sum so far
  // And the maximum subarray sum ending at the current element
  int max_so_far = arr[0];
  int max_ending_here = arr[0];

  // Iterate through the array starting from the second element
  for (int i = 1; i < n; i++) {
    // If the current subarray sum is positive, add the current element to it
    if (max_ending_here > 0) {
      max_ending_here = max_ending_here + arr[i];
    }
    // Otherwise, start a new subarray sum from the current element
    else {
      max_ending_here = arr[i];
    }

    // Update the maximum subarray sum so far
    // If the maximum subarray ending at the current element is greater
    max_so_far = std::max(max_so_far, max_ending_here);
  }

  // Return the maximum subarray sum so far
  std::cout << "Maximum Subarray Sum for array [";
  for (int i = 0; i < n; i++) {
    std::cout << arr[i] << ", ";
  }
  std::cout << "] is " << max_so_far << std::endl;
  return max_so_far;
}

int main() {
  int arr[] = {2, -3, 4, 1};
  int n = sizeof(arr) / sizeof(arr[0]);
  findMaxSubarraySum(arr, n);
  return 0;
}


// Function to find the maximum subarray sum
function findMaxSubarraySum(arr) {
  // Initialize the maximum subarray sum so far
  // And the maximum subarray sum ending at the current element
  let maxSoFar = arr[0];
  let maxEndingHere = arr[0];

  // Iterate through the array starting from the second element
  for (let i = 1; i < arr.length; i++) {
    // If the current subarray sum is positive, add the current element to it
    if (maxEndingHere > 0) {
      maxEndingHere = maxEndingHere + arr[i];
    }
    // Otherwise, start a new subarray sum from the current element
    else {
      maxEndingHere = arr[i];
    }

    // Update the maximum subarray sum so far
    // If the maximum subarray ending at the current element is greater
    maxSoFar = Math.max(maxSoFar, maxEndingHere);
  }

  // Return the maximum subarray sum so far
  console.log(`Maximum Subarray Sum for array ${arr} is ${maxSoFar}`);
  return maxSoFar;
}

// Example usage
findMaxSubarraySum([2, -3, 4, 1]);


import java.util.Arrays;

public class Main {
  public static int findMaxSubarraySum(int[] arr) {
    // Initialize the maximum subarray sum so far
    // And the maximum subarray sum ending at the current element
    int maxSoFar = arr[0];
    int maxEndingHere = arr[0];

    // Iterate through the array starting from the second element
    for (int i = 1; i < arr.length; i++) {
      // If the current subarray sum is positive, add the current element to it
      if (maxEndingHere > 0) {
        maxEndingHere = maxEndingHere + arr[i];
      }
      // Otherwise, start a new subarray sum from the current element
      else {
        maxEndingHere = arr[i];
      }

      // Update the maximum subarray sum so far
      // If the maximum subarray ending at the current element is greater
      maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    // Return the maximum subarray sum so far
    System.out.println("Maximum Subarray Sum for array " + Arrays.toString(arr) + " is " + maxSoFar);
    return maxSoFar;
  }

  public static void main(String[] args) {
    findMaxSubarraySum(new int[]{2, -3, 4, 1});
  }
}

Time & Space Complexities:

The time complexity of Kadane’s algorithm is O(n), where n is the size of the input array. This is because the algorithm iterates through the array once, performing a constant number of operations for each element.

The space complexity of Kadane’s algorithm is O(1), which means it uses a constant amount of additional space, regardless of the size of the input array. The algorithm only requires a few variables to keep track of the current maximum subarray sum and the overall maximum subarray sum, and it does not need to create any additional data structures that grow with the input size.

Intuition Behind the Algorithm

At each element, Kadane’s algorithm tries to find out the maximum possible sum among all subarray’s ending at the current element. In order to compute it efficiently, we have two options:

Add current element to the maximum subarray sum ending at the previous element
Start a new subarray starting from the current element and reset the maximum subarray sum ending at current element to it’s value

If the maximum subarray sum ending at the previous element is negative or zero, then going with option 1 will further reduce the subarray sum ending at current element. So we start a new subarray starting from the current element and go with option 2.

If the maximum subarray sum ending at the previous element is positive, it makes sense to use it when considering the maximum subarray ending at current element. So we go with option 1.

By doing this, Kadane’s algorithm is able to efficiently find the maximum subarray in a single pass through the array, without having to try every possible subarray.

TODO: Add animation showing all the steps.