What is Kadanes Algorithm?

This blog covers all about Kadane’s algorithm, from its fundamentals to codes in various programming languages like C++, Java, and Python. Further, we will be exploring both brute force and dynamic programming approaches to find the maximum subarray. 

Table of Contents

• What is a Subarray?
• What is the Maximum Subarray Problem?
• What is Kadane’s Algorithm?
• Steps for Implementing Kadane’s Algorithm
• Pseudocode of Kadane’s Algorithm
• How Does Kadene’s Algorithm Work?
• Time Complexity of Kadane’s Algorithm
• Code for Brute Force Approach
• What is Dynamic Programming?
• Code for Kadane’s Algorithm Using Dynamic Programming
• Advantages of Kadane’s Algorithm
• Disadvantages of Kadane’s Algorithm
• FAQs

Learn data structures and algorithms in this comprehensive video course:

What is a Subarray?

A subarray is a part of an array made up of consecutive elements. It’s like if you have given a list of numbers, a subarray will be a section of that list that contains numbers that are next to each other. For example, in the array [1, 2, 3, 4], possible subarrays can be [1, 2], [2, 3, 4], [1, 2, 3, 4], etc. The subarray maintains the order of elements and occurs within the array itself. 

What is the Maximum Subarray Problem?

The maximum subarray problem, also known as the maximum segment sum problem, is the task of finding a contiguous subarray with the largest sum within a given one-dimensional array of numbers. There are two methods to solve the maximum subarray problem: Kadane’s algorithm and the divide-and-conquer approach. Both have their own advantages and disadvantages for different applications.

Let’s understand the maximum subarray problem with the help of one example:

Consider the array A = [-2, -1, 5, -3, 2, -1, 4]

The maximum subarray is [5, -3, 2, -1, 4] with the sum of its elements equal to 7, while if you look at the sum of all the elements of the original array, it will be 4.

What is Kadane’s Algorithm?

Kadane’s algorithm is a dynamic programming algorithm that efficiently solves the maximum subarray problem in linear time complexity, O(n), where n is the size of the input array. It operates by iterating through the array. It keeps track of the maximum sum of a continuous subarray encountered earlier, and this way we get the maximum subarray sum. The algorithm is an important part of data structure and algorithms and is widely used in various applications due to its simplicity and effectiveness. 

Steps for Implementing Kadane’s Algorithm

Here are the steps to implement Kadane’s algorithm:

Step 1: Initialization of Variables

In Kadane’s algorithm, two variables are maintained throughout the iteration:

• current_max: This variable stores the maximum sum of the continuous subarray that ends at the current index, and we will initialize it with 0.
• global_max: This variable stores the maximum overall sum of any subarray that is encountered in any previous iteration, and we will initialize it with min integer value or ‘INT_MIN’.

Step 2: Iterate the array (arr[ ]) with the help of any loop. Here, we will be iterating the array with the help of the ‘for’ loop.

Step 3: For each element of the array ‘i’ calculate the sum of ‘i’ and  current_max.

               Formula : current_sum = current_max + i

Step 4: Update current_max with the maximum of 0 and current _sum:

              current_max = max(0, current_sum)

Step 5: Check if the current value of current-max is greater than global_max. If it is greater than global_max than update global_max with current_max:

               global_max = max(global_max , current_max)     

Step 6: Once we iterate the complete array, the value of global_max will be the sum of elements of the maximum continuous subarray of the original array.

Pseudocode of Kadane’s Algorithm

With the help of this pseudocode, we can write code for Kadane’s algorithm easily:

Initialize:

     global_max = INT_MIN
     current_max = 0
Loop for iteration of each element of the array
current_max = current_max + a[i]
if(global_maxr < current_max)
            global_max = current_max
if(current_max < 0)
           current_max = 0
return global_max

How Does Kadene’s Algorithm Work?

Kadane’s algorithm works by maintaining two variables (current sum and maximum sum) during the iteration through the array: the current sum (can be denoted as current_max) and the maximum sum encountered in the previous iteration (can be denoted as global_max). Initially, both current_max and global_max are set to the value of the first element in the array.

The algorithm starts by iterating through an array, which starts with the second element. At each iteration, the sum of the current element is calculated along with the current maximum sum. Then we compare this sum with the current element itself. If the current element is greater than the sum of the current element and current_max, the algorithm updates current_max by the value of the current element; otherwise, it adds the current element to current_max.

Simultaneously, the algorithm checks if current_max is greater than global_max. If so, it updates global_max to the value of current_max.

This process continues as the algorithm moves through the array. Ultimately, the global_max variable stores the maximum sum of a continuous subarray within the given array.

Time Complexity of Kadane’s Algorithm

Time complexity is a major reason for choosing Kadane’s algorithm for solving maximum subarray problems over the brute force approach because of the linear time complexity. The time complexity of the brute force algorithm is O(n^3), as Kadane’s algorithm has O(n) time complexity, which makes the code more efficient.

Code for Brute Force Approach

Here, we have given code based on the brute force approach to solving maximum subarray problems in C++, Java, and Python:

Brute Force Approach in C++

#include <iostream>
using namespace std;
int main() {
  int n;
  cin >> n;
  int arr[n];
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
  }
  int max_sum = INT_MIN;
  for (int i = 0; i < n; i++) {
    for (int j = i; j < n; j++) {
      int sum = 0;
      for (int k = i; k <= j; k++) {
        sum += arr[k];
      }
      if (sum > max_sum) {
        max_sum = sum;
      }
    }
  }
  cout << "Maximum subarray sum: " << max_sum << endl;
  return 0;
}

Brute Force Approach in Java

public class MaximumSubarrayBruteForce {
    public static int findMaxSubarraySum(int[] arr) {
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            for (int j = i; j < arr.length; j++) {
                int sum = 0;
                for (int k = i; k <= j; k++) {
                    sum += arr[k];
                }
                maxSum = Math.max(maxSum, sum);
            }
        }
        return maxSum;
    }
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSubarraySum = findMaxSubarraySum(arr);
        System.out.println("Maximum subarray sum: " + maxSubarraySum);
    }
}

Brute Force Approach in Python

def find_max_subarray_sum(arr):
    max_sum = int(float('-Inf'))
    for i in range(len(arr)):
        for j in range(i, len(arr)):
            subarray_sum = 0
            for k in range(i, j + 1):
                subarray_sum += arr[k]
            max_sum = max(max_sum, subarray_sum)
    return max_sum
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray_sum = find_max_subarray_sum(arr)
print("Maximum subarray sum:", max_subarray_sum)

What is Dynamic Programming?

Dynamic programming is a method used for solving complex programming problems by breaking them into simpler subproblems. Working on this technique involves solving each subproblem only once and then storing its solution to avoid repetitive computations that ultimately help reduce time complexity and optimize the code. Some of its popular applications include code optimization and solving AI or machine learning problems. This approach efficiently solves problems that contain overlapping substructures.

Code for Kadane’s Algorithm Using Dynamic Programming

Kadane’s algorithm follows a dynamic programming approach to find the subarray with elements having the maximum sum. Here are the codes for Kadane’s algorithm in C++, Java, and Python.

Kadane’s Algorithm in C++

#include <iostream>
using namespace std;
int kadanesAlgorithm(int arr[], int n) {
    int current_max = 0;
    int global_max = INT_MIN;
    for (int i = 0; i < n; i++) {
        current_max += arr[i];
        if (current_max > global_max) {
            global_max = current_max;
        }
        if (current_max < 0) {
            current_max = 0;
        }
    }
    return global_max;
}
int main() {
    int n;
    cin >> n;
    int arr[n];
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    int max_subarray_sum = kadanesAlgorithm(arr, n);
    cout << "Maximum subarray sum: " << max_subarray_sum << endl;
    return 0;
}

Kadane’s Algorithm in Java

public class KadanesAlgorithm {
    public static int findMaxSubarraySum(int[] arr) {
        int current_max = 0;
        int global_max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            current_max = Math.max(0, current_max + arr[i]);
            global_max = Math.max(global_max, current_max);
        }
        return global_max;
    }
    public static void main(String[] args) {
        int[] arr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int maxSubarraySum = findMaxSubarraySum(arr);
        System.out.println("Maximum subarray sum: " + maxSubarraySum);
    }
}

Kadane’s Algorithm in Python

def kadane_algorithm(arr):
    """Finds the maximum contiguous subarray sum in an array."""
    current_max = 0
    global_max = float('-inf')  # Initialize the maximum sum to minus infinity
    for i in arr:
        current_max = max(0, current_max + i)
        global_max = max(global_max, current_max)
    return global_max
# Example usage
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
max_subarray_sum = kadane_algorithm(arr)
print("Maximum subarray sum:", max_subarray_sum)

Advantages of Kadane’s Algorithm

Here are the reasons why Kadane’s algorithm is so popular among coders:

• Kadane’s algorithm finds the maximum subarray sum in linear time complexity, which is O(n), which makes it very convenient for solving complex and large datasets. 
• It has constant space complexity because it works only with two variables.
• It is comparatively easy to implement compared to similar algorithms like divide and conquer. 

Disadvantages of Kadane’s Algorithm

Kadane’s algorithm is an efficient and widely used algorithm for finding the maximum continuous subarray sum, but some limitations are as follows:

• Kadane’s algorithm is unable to find a non-contiguous subarray with a maximum sum.
• Kadane’s algorithm is designed to work only when there is at least one positive integer in the array. Thus, it cannot be used to find the maximum subarray in the array with all negative integers.

FAQs