Kadane’s Algorithm

Last Updated on March 23, 2023 by Prepbytes

If you’re here, it’s because you were trying to solve the "Maximum Subarray Sum Problem" and came across Kadane’s Algorithm but couldn’t figure out how something like that works. Or maybe you were bored of using Kadane’s Algorithm as a "black box". Or perhaps you wanted to know the dynamic programming aspect of it. Or maybe you just want to learn about a new approach that will help you become a better programmer. Whatever your motivation, you’ve come to the perfect place. Here we look at how to approach this problem using brute force, and then work toward improving our approach and coming up with a better algorithm, aka Kadane’s Algorithm. So, let’s get started.

How to Find Maximum Sum Subarray

Given an array of integers, the task is to find the maximum subarray sum possible of all the non-empty arrays.

Input: [−2, 1, −3, 4, −1, 2, 1, −5, 4]
Output: 6

Explanation: Subarray [4, −1, 2, 1] is the max sum contiguous subarray with a sum of 6.

We would tackle this problem in the following two ways:

• Simple Approach
• Optimized Approach: Kadane’s Algorithm

Simple Approach

A simple approach to solving the Maximum Subarray Sum problem involves using two nested loops to iterate through all possible subarrays and calculate their sum. The subarray with the maximum sum is then returned as the solution.

The algorithm works as follows:

• Step – 1 Run a loop for i ranging from 0 to n – 1, where n is the size of the array.
• Step – 2 Now, we’ll run a nested loop for j from i to n – 1 and add the value of the element at index j to the variable sum.
• Step – 3 If the value of the variable sum is greater than the variable max_sum at any point, then we will update the value of max_sum.
• Step – 4 return max_sum.

The time complexity of this algorithm is O(N^2) because it involves two nested loops, making it less efficient than Kadane’s algorithm. For an array of size N, the number of subarrays is N*(N+1)/2, and each subarray takes O(N) time to compute the sum.

Although this algorithm is not the most efficient way to solve the problem, it is still useful in situations where the input size is small or when the input is not expected to change frequently.

#include <iostream>
#include <climits>
using namespace std;

int maxSubarraySum(int arr[], int n)
{
    int max_sum = INT_MIN;
    for (int i = 0; i < n; i++)
    {
        int sum = 0;
        for (int j = i; j < n; j++)
        {
            sum += arr[j];
            if (sum > max_sum)
            {
                max_sum = sum;
            }
        }
    }
    return max_sum;
}

int main()
{
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    int max_sum = maxSubarraySum(arr, n);
    cout << "Maximum subarray sum is " << max_sum << endl;
    return 0;
}

class MaxSubarraySum
{
    public static int maxSubarraySum(int[] arr, int n)
    {
        int max_sum = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            for (int j = i; j < n; j++)
            {
                sum += arr[j];
                if (sum > max_sum)
                {
                    max_sum = sum;
                }
            }
        }
        return max_sum;
    }

    public static void main(String[] args)
    {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int n = arr.length;
        int max_sum = maxSubarraySum(arr, n);
        System.out.println("Maximum subarray sum is " + max_sum);
    }
}

def maximumSubarraySum(arr):
    n = len(arr)
    maxSum = -1e8

    for i in range(0, n):
        currSum = 0
        for j in range(i, n):
            currSum = currSum + arr[j]
            if(currSum > maxSum):
                maxSum = currSum

    return maxSum

if __name__ == "__main__":
    a = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
    print(maximumSubarraySum(a));

Kadane’s Algorithm

Kadane’s algorithm is an efficient algorithm used to find the maximum sum subarray within a given array of integers. It was proposed by computer scientist Jay Kadane in 1984.

The algorithm works by maintaining two variables: "max_so_far" and "max_ending_here". "max_so_far" keeps track of the maximum sum subarray found so far, while "max_ending_here" keeps track of the maximum sum of subarray ending at the current position.

The algorithm iterates through the array, updating "max_ending_here" by adding the current element to it if it is positive, or setting it to zero if it is negative. It also updates "max_so_far" if "max_ending_here" becomes greater than it.

Here is the step-by-step process for Kadane’s algorithm:

• Step – 1 Initialize two variables, "max_so_far" and "max_ending_here", as 0.
• Step – 2 Loop through each element of the array:
• Step – 3 Add the current element to "max_ending_here".
  • If "max_ending_here" is negative, set it to 0.
  • If "max_ending_here" is greater than "max_so_far", update "max_so_far" to "max_ending_here".
• Step – 4 Return "max_so_far".

Overall, Kadane’s algorithm has a time complexity of O(n), where n is the length of the input array, making it a very efficient solution for finding maximum sum subarrays.

Dry Run of Kadane’s Algorithm

Here is a step-by-step explanation of the dry run of Kadane’s algorithm:

Suppose we have given an integer array: arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

1. For i = 0,   max_ending_here = max_ending_here + a[i] = 0 + -2 = -2, Since max_ending_here < 0, max_ending_here = 0.

2. For i = 1,   max_ending_here = max_ending_here + a[i] = 0 + 1 = 1, Since max_ending_here > max_so_far, max_so_far = max_ending_here = 1.

3. For i = 2,   max_ending_here = max_ending_here + a[i] = 1 + -3 = -2, Since max_ending_here < 0, max_ending_here = 0.

4. For i = 3,   max_ending_here = max_ending_here + a[i] = 0 + 4 = 4, Since max_ending_here > max_so_far, max_so_far = max_ending_here = 4.

5. For i = 4,   max_ending_here = max_ending_here + a[i] = 4 + -1 = 3

6. For i = 5,   max_ending_here = max_ending_here + a[i] = 3 + 2 = 5, Since max_ending_here > max_so_far, max_so_far = max_ending_here = 5.

7. For i = 6,   max_ending_here = max_ending_here + a[i] = 5 + 1 = 6, Since max_so_far < max_ending_here, max_so_far = max_ending_here = 6.

8. For i = 7,   max_ending_here = max_ending_here + a[i] = 6 + -5 = 1.

9. For i = 7,   max_ending_here = max_ending_here + a[i] = 1 + 4 = 5.

After the loop finishes, max_so_far will contain the maximum sum of any contiguous subarray in the array. In this case, max_so_far will be 6, which is the sum of the subarray [4, -1, 2, 1].

Code for Kadane’s Algorithm

Let's go into the implementation of Kadane's algorithm for various languages after knowing how Kadane’s Algorithm actually works.

#include <algorithm>
#include <iostream>
#include <bits/stdc++.h>

using namespace std;
int maximumSubarraySum(vector<int> arr) {
  int n = arr.size();
  int max_so_far = 0;
  int max_ending_here = 0;
  for(int i = 0; i < n; i++) {
    	max_ending_here += arr[i];
    	if(max_ending_here < 0) {
        	max_ending_here = 0;
    	}	
    	if(max_so_far < max_ending_here) {
        	max_so_far = max_ending_here;
    	}
  }
  return max_so_far;
}
int main() {
    vector<int> arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    cout << maximumSubarraySum(arr) << endl;
    return 0;
}

class Kadane {
    public static int maximumSubarraySum(int[] arr) {
        int max_so_far = 0;
        int max_ending_here = 0;
        for(int i = 0; i < arr.length; i++) {
            max_ending_here += arr[i];
            if(max_ending_here < 0) {
                max_ending_here = 0;
            }
            if(max_so_far < max_ending_here) {
                max_so_far = max_ending_here;
            }
        }
        return max_so_far;
    }
    
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maximumSubarraySum(arr));
    }
}

def max_subarray_sum(arr):
    max_so_far = arr[0]
    max_ending_here = arr[0]

    for i in range(1, len(arr)):
        max_ending_here = max(arr[i], max_ending_here + arr[i])
        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_sum = max_subarray_sum(arr)
print("Maximum sum of contiguous subarray:", max_sum)

Conclusion
Kadane's algorithm is a popular algorithm used to find the maximum sum of any contiguous subarray in a given array of integers. The algorithm works by iterating over the array and keeping track of the maximum sum seen so far and the maximum sum ending at the current index. Kadane's algorithm is efficient, with a time complexity of O(n) and a space complexity of O(1), which means it uses a constant amount of memory.

FAQs

Here are some frequently asked questions (FAQs) about Kadane's algorithm:

Q1: Is Kadane's algorithm suitable for finding the maximum sum of a non-contiguous subarray?
Ans: No, Kadane's algorithm is only suitable for finding the maximum sum of a contiguous subarray.

Q2: Can Kadane's algorithm handle arrays with negative numbers?
Ans: Yes, Kadane's algorithm can handle arrays with negative numbers.

Q3: What is the output of Kadane's algorithm if all the elements in the array are negative?
Ans: The output of Kadane's algorithm in this case would be the smallest negative number in the array.

Q4: Is Kadane's algorithm a divide-and-conquer algorithm?
Ans: No, Kadane's algorithm is not a divide-and-conquer algorithm.

Q5: Can Kadane's algorithm be used to solve the maximum subarray problem in two-dimensional arrays?
Ans: No, Kadane's algorithm is only suitable for one-dimensional arrays.

Q6: Can Kadane's algorithm be used to find the maximum product of any contiguous subarray?
Ans: No, Kadane's algorithm is only suitable for finding the maximum sum of any contiguous subarray, not the maximum product.

Q7: How can Kadane's algorithm be modified to find the subarray itself, not just its sum?
Ans: One way to modify Kadane's algorithm is to keep track of the starting and ending indices of the maximum subarray seen so far, in addition to the maximum sum seen so far.