Kadane's Algorithm: Find Maximum Subarray Sum in an Array

Master Kadane's algorithm to solve the maximum subarray problem in O(n) time. Complete guide with Python, Java, and C++ implementations.

What is the maximum subarray sum problem?

The maximum subarray sum problem is used to identify a contiguous subarray with the largest sum from a one-dimensional array of numbers. For example, if we have an array [2, 3, -5, 6, -4], we need to find a contiguous subarray with the maximum sum. In this case, the contiguous subarray with the maximum sum will be [2, 3, -5, 6], with the sum 6. How do we find this?

Any given 1D array with N elements has N(N+1)/2 contiguous subarrays. For example, the array [2, 3, -5, 6, -4] has five elements. Hence, it will have fifteen subarrays, as shown in the following image:

Subarrays of an array

To find the subarray having the maximum sum, we can find all the subarrays of a given array and get the maximum sum by calculating the sum of all the subarrays. We do precisely this in the brute-force approach to find the maximum subarray sum.

Related Course

Learn Advanced Algorithms with Python: String Searching Algorithms

Learn about two powerful string searching methodologies: the Rabin-Karp algorithm and the Knuth-Morris-Pratt algorithm.Try it for free

Find the maximum subarray sum using the brute-force approach

To find the maximum subarray sum using the brute-force approach, we start with the first element of the array (index 0) and calculate the sum of all the subarrays beginning at index 0. Next, we move to index 1 and find the sum of all the subarrays starting at index 1. We keep doing this until we calculate the sum of all the subarrays. In this process, we keep track of the maximum subarray sum and update it if we find a new maximum.

We can define the entire process using the following steps:

We will initialize a variable i to 0 to store the start index of a subarray and a variable n to store the length of the input array.
For a given start index i, we will use a nested for loop with index j, ranging from i to n - 1 to store the end index of subarrays that start from index i and end at index j.
For every j, we will initialize a current_sum variable to 0 to store the sum of elements in the subarray starting at index i and ending at index j. Then, we will use a third loop with index k running from i to j to calculate the sum of elements in the subarray.
- For each k, we will add the element at index k to the current_sum variable.
- After the inner loop finishes, current_sum will contain the total sum of the current subarray. We will compare current_sum with the maximum subarray sum and update the maximum value if we find a new maximum.
After calculating the sum of the subarrays starting at a given index i, we will increment i by one and repeat steps 2 and 3.
We will continue this process until i<n. After that, we will get the max subarray sum.

To convert these steps to code, we will first convert it into a pseudocode as follows:

Input: An array A of length n 
Output: Maximum subarray sum 
 
# Initialize the maximum subarray sum to negative infinity 
max_sum ← -∞ 
 
# Select the starting index of a subarray 
for i from 0 to n - 1: 
    # Select the end index of a subarray 
    for j from i to n - 1: 
        # Initialize the sum of the current subarray to 0 
        current_sum ← 0 
        # Find the sum of the current subarray 
        for k from i to j: 
            current_sum ← current_sum + A[k] 
        # Check if the sum of the current subarray is greater than the maximum subarray sum. 
        #If yes, update the maximum subarray sum to the current subarray sum. 
        if current_sum > max_sum: 
            max_sum ← current_sum 
 
return max_sum

We can implement this pseudocode in any language to get the maximum subarray sum for a given array. The C++ implementation for the maximum subarray sum problem using the brute-force approach is as follows:

#include <iostream> 
#include <vector> 
#include <climits> 
using namespace std; 
 
int max_subarray_sum(vector<int> arr) { 
    // Get the length of the input array 
    int l = arr.size(); 
    // Initialize the maximum subarray sum to negative infinity 
    int max_sum = INT_MIN; 
     
    // Select the starting index of a subarray 
    for (int i = 0; i < l; i++) { 
        // Select the end index of a subarray 
        for (int j = i; j < l; j++) { 
            // Initialize the sum of the current subarray to 0 
            int current_sum = 0; 
            // Find the sum of the current subarray 
            for (int k = i; k <= j; k++) { 
                current_sum += arr[k]; 
            } 
            // Check if the sum of the current subarray is greater than the maximum subarray sum. 
            // If yes, update the maximum subarray sum to the current subarray sum. 
            if (current_sum > max_sum) { 
                max_sum = current_sum; 
            } 
        } 
    } 
    return max_sum; 
} 
 
int main() { 
    vector<int> arr = {2, 3, -5, 6, -4}; 
    cout << "The input array is: "; 
    for (int i : arr) { 
        cout << i << " "; 
    } 
    cout << endl; 
 
    int result = max_subarray_sum(arr); 
    cout << "The maximum subarray sum is: " << result << endl; 
 
    return 0; 
} 

Copy to clipboardCopy to clipboard

Output:

The input array is: 2 3 -5 6 -4  
The maximum subarray sum is: 6 

Copy to clipboardCopy to clipboard

The brute-force approach to solving the maximum subarray sum problem uses three for loops that traverse the elements of the input array to find the maximum subarray sum. This results in O(n³) time complexity, which isn’t appropriate for arrays with a large number of elements. Hence, we can remove a for loop to improve the time complexity to O(n²). Let’s discuss how to do this.

Find maximum subarray sum in O(n²) time

In the brute-force solution, we compute the sum for each subarray between indices i and j from scratch using the third loop. However, if we already know the sum of elements from index i to j-1, we can find the sum of elements from index i to j by adding the element at index j to the sum of elements from index i to j-1.

 $\text{Sum of elements from index i to index j} = \text{Sum of elements from index i to index j-1} + \text{element at index j}$

Using this approach, we can eliminate the innermost loop and compute the sum of each subarray incrementally in O(1) time. This will reduce the time complexity of the solution to O(n²).

We can implement this solution using the following steps:

We will initialize a variable i to 0 to store the start index of a subarray and a variable n to store the length of the input array.
For a given start index i, we will initialize a current_sum variable to 0 to store the sum of elements in the subarrays starting at index i.
Next, we will use a nested for loop with index j, ranging from i to n – 1 to store the end index of subarrays which start from index i and end at index j.
- For every j, we will calculate the sum of the subarrays from index i to j by adding the element at index j to the sum of elements from index i to j-1.
- After getting the sum of the elements of the current subarray, we will compare it with the maximum subarray sum and update the maximum value.
After calculating the sum of all the subarrays starting at index i, we will increment i by one and repeat steps 2 and 3.
We will continue this process until i<n. After that, we will get the max subarray sum. We can convert these steps to pseudocode as follows:

Input: An array A of length n 
Output: Maximum subarray sum 
 
# Initialize the maximum subarray sum to negative infinity 
max_sum ← -∞ 
 
# Select the starting index of a subarray 
for i from 0 to n - 1: 
 
    # Initialize the sum of the current subarray to 0 
    current_sum ← 0 
 
    # Select the end index of a subarray 
    for j from i to n - 1: 
        # Find the sum of the current subarray 
        current_sum ← current_sum + A[j] 
        # Check if the sum of the current subarray is greater than the maximum subarray sum. 
        #If yes, update the maximum subarray sum to the current subarray sum. 
        if current_sum > max_sum: 
            max_sum ← current_sum 
 
return max_sum

As we have the pseudo code now, we can implement the maximum subarray sum problem with O(n²) time complexity in C++ as follows:

#include <iostream> 
#include <vector> 
#include <climits> 
using namespace std; 
 
int max_subarray_sum(vector<int> arr) { 
    // Get the length of the input array 
    int l = arr.size(); 
    // Initialize the maximum subarray sum to negative infinity 
    int max_sum = INT_MIN; 
    // Select the starting index of a subarray 
    for (int i = 0; i < l; i++) { 
        // Initialize the sum of the subarray starting at index i to 0 
        int current_sum = 0; 
        // Select the end index of a subarray 
        for (int j = i; j < l; j++) { 
            // Find the sum of the subarray ending at index j 
            current_sum = current_sum + arr[j]; 
            // Check if the sum of the current subarray is greater than the maximum subarray sum. 
            // If yes, update the maximum subarray sum to the current subarray sum. 
            if (current_sum > max_sum) { 
                max_sum = current_sum; 
            } 
        } 
    } 
    return max_sum; 
} 
 
int main() { 
    vector<int> arr = {2, 3, -5, 6, -4}; 
    cout << "The input array is: "; 
    for (int num : arr) { 
        cout << num << " "; 
    } 
    cout << endl; 
     
    int result = max_subarray_sum(arr); 
    cout << "The maximum subarray sum is: " << result << endl; 
 
    return 0; 
} 

Copy to clipboardCopy to clipboard

Output:

The input array is: 2 3 -5 6 -4  
The maximum subarray sum is: 6 

Copy to clipboardCopy to clipboard

We can improve on the O(n²) solution to get the maximum subarray sum in O(n) time. For this, we use Kadane’s algorithm. Let’s discuss how it works.

What is Kadane’s algorithm?

Kadane’s algorithm is a dynamic programming algorithm we use to solve the maximum subarray sum problem in linear time. While using Kadane’s algorithm to find the maximum subarray sum, we traverse the input array only once. While traversing the input array, Kadane’s algorithm assumes that we only need to know the maximum subarray ending at index j-1 to find the maximum subarray ending at index j. Using this assumption, Kadane’s algorithm uses the following process to check for the maximum subarray sum:

First, we will initialize the maximum subarray sum to the first element of the array and a variable current_sum to the first element of the array to keep track of the sum of a selected maximum subarray.
Next, we will start from the second element of the array (index 1) and traverse the array till the last element using a for loop.
- At each index, we will calculate the combined sum of the current element and the running sum of the previous maximum subarray, current_sum.
  - If the combined sum is less than the current element, the previous subarray sum current_sum will be negative. Hence, we will begin a new subarray at the current index and update current_sum to the current element.
  - If the combined sum exceeds the current element, we will extend the previous subarray by including the current element and update current_sum to the combined sum.
- After getting the new subarray and its sum in the current_sum variable, we will compare it with the maximum subarray sum and update the maximum subarray sum if we find a new maximum.
After executing the for loop, we get the maximum subarray sum.

The pseudocode to find the maximum subarray sum using Kadane’s algorithm is as follows:

Input: An array A of length n 
Output: Maximum subarray sum 
 
# Initialize the running subarray sum and the maximum subarray sum to the first element in the array 
current_sum ← A[0] 
max_sum ← A[0] 
 
# Select an index of a subarray 
for i from 1 to n - 1: 
    # Get the sum of previous subarray elements and the current element 
    combined_sum = current_sum + A[i] 
 
    # If the current element greater than combined sum, update current_sum to the current element, otherwise update it to the combined sum 
    if A[i] > combined_sum: 
        current_sum ← A[i] 
    else: 
        current_sum ← combined_sum 
 
    # Update the maximum subarray sum 
    if current_sum > max_sum: 
        max_sum ← current_sum 
 
return max_sum

You can convert this pseudocode to code in the language of your choice.

Find maximum subarray sum using Kadane’s algorithm in O(n) time

We will implement the maximum subarray sum problem using Kadane’s algorithm in Python, Java, and C++.

Python implementation

In Python, you can implement the solution for the maximum subarray sum problem using Kadane’s algorithm as follows:

def max_subarray_sum(arr): 
    # Get the length of the input array 
    l=len(arr) 
    # Initialize the running subarray sum and the maximum subarray sum to the first element in the array 
    max_sum = arr[0] 
    current_sum = arr[0] 
    # Select an index of a subarray 
    for i in range(1,l): 
        # Get the sum of previous subarray elements and the current element 
        combined_sum  = current_sum + arr[i] 
 
        # If the current element is greater combined_sum, update current_sum to the current element, otherwise update it to combined_sum 
        if arr[i] > combined_sum : 
            current_sum= arr[i]  
        else: 
            current_sum= combined_sum 
        # Update the maximum subarray sum 
        if current_sum>max_sum: 
            max_sum=current_sum 
             
    return max_sum 
 
arr = [2, 3, -5, 6, -4] 
print("The input array is:",arr) 
result=max_subarray_sum(arr) 
print("The maximum subarray sum is:", result) 

Copy to clipboardCopy to clipboard

Output:

The input array is: [2, 3, -5, 6, -4] 
The maximum subarray sum is: 6 

Copy to clipboardCopy to clipboard

Java implementation

You can implement Kadane’s algorithm in Java as follows:

import java.util.*; 
 
public class MaxSubarraySum { 
 
    public static int max_subarray_sum(int[] arr) { 
        // Get the length of the input array 
        int l = arr.length; 
        // Initialize the running subarray sum and the maximum subarray sum to the first element in the array 
        int max_sum = arr[0]; 
        int current_sum = arr[0]; 
        // Select an index of a subarray 
        for (int i = 1; i < l; i++) { 
            // Get the sum of previous subarray elements and the current element 
            int combined_sum = current_sum + arr[i]; 
 
            // If the current element is greater than combined_sum, update current_sum to the current element, otherwise update it to combined_sum 
            if (arr[i] > combined_sum) { 
                current_sum = arr[i]; 
            } else { 
                current_sum = combined_sum; 
            } 
 
            // Update the maximum subarray sum 
            if (current_sum > max_sum) { 
                max_sum = current_sum; 
            } 
        } 
        return max_sum; 
    } 
 
    public static void main(String[] args) { 
        int[] arr = {2, 3, -5, 6, -4}; 
        System.out.println("The input array is: " + Arrays.toString(arr)); 
        int result = max_subarray_sum(arr); 
        System.out.println("The maximum subarray sum is: " + result); 
    } 
} 

Copy to clipboardCopy to clipboard

Output:

The input array is: [2, 3, -5, 6, -4] 
The maximum subarray sum is: 6 

Copy to clipboardCopy to clipboard

C++ implementation

You can implement the solution for the maximum subarray sum problem using Kadane’s algorithm in C++ as follows:

#include <iostream> 
#include <vector> 
using namespace std; 
 
int max_subarray_sum(vector<int> arr) { 
    // Get the length of the input array 
    int l = arr.size(); 
    // Initialize the running subarray sum and the maximum subarray sum to the first element in the array 
    int max_sum = arr[0]; 
    int current_sum = arr[0]; 
    // Select an index of a subarray 
    for (int i = 1; i < l; i++) { 
        // Get the sum of previous subarray elements and the current element 
        int combined_sum = current_sum + arr[i]; 
 
        // If the current element is greater than combined_sum, update current_sum to the current element, otherwise update it to combined_sum 
        if (arr[i] > combined_sum) { 
            current_sum = arr[i]; 
        } else { 
            current_sum = combined_sum; 
        } 
 
        // Update the maximum subarray sum 
        if (current_sum > max_sum) { 
            max_sum = current_sum; 
        } 
    } 
    return max_sum; 
} 
 
int main() { 
    vector<int> arr = {2, 3, -5, 6, -4}; 
    cout << "The input array is: "; 
    for (int num : arr) { 
        cout << num << " "; 
    } 
    cout << endl; 
 
    int result = max_subarray_sum(arr); 
    cout << "The maximum subarray sum is: " << result << endl; 
 
    return 0; 
} 

Copy to clipboardCopy to clipboard

Output:

The input array is: 2 3 -5 6 -4  
The maximum subarray sum is: 6 

Copy to clipboardCopy to clipboard

We have implemented the optimal solution for the maximum subarray sum problem in Python, Java, and C++. Sometimes, we also need to find the indices of the subarray with the maximum sum. Let’s discuss how to do so.

Find maximum subarray sum with array indices

To find the maximum subarray sum with array indices, we will make the following changes to the solution of the maximum subarray sum problem.

We will initialize two variables, start and end, to store the subarray’s start and end indices with the maximum sum.
We will also initialize a temp_start variable to keep track of the start index of the current subarray.
Whenever we start a new subarray, we will set temp_start to the index of the current element in the array.
Whenever we find a maximum subarray sum ending at an element, we will set the end variable to the index of the current element in the array. We will also assign the value in the temp_start to the start variable to get the indices of the maximum subarray sum ending at the current element.

After making the above changes, we will get the start and end indices of the maximum subarray sum in the start and end variables, as shown in the following pseudocode.

Input: An array A of length n 
Output: Maximum subarray sum and its start and end indices 
 
# Initialize the running subarray sum and the maximum subarray sum to the first element in the array 
current_sum ← A[0] 
max_sum ← A[0] 
 
# Initialize indices with 0 
start ← 0 
end ← 0 
temp_start ← 0 
 
 
# Select an index of a subarray 
for i from 1 to n - 1: 
    # Get the sum of previous subarray elements and the current element 
    combined_sum = current_sum + A[i] 
 
    # If the current element is greater than combined_sum, update current_sum to the current element, otherwise update it to the combined_sum 
    if A[i] > combined_sum: 
        current_sum ← A[i] 
        # Start the subarray at i 
        temp_start ← i 
    else: 
        current_sum ← combined_sum 
 
    # Update the maximum subarray sum 
    if current_sum > max_sum: 
        max_sum ← current_sum 
 
        # Update the start and end indices of the subarray with the maximum sum 
        start ← temp_start 
        end ← i 
 
return max_sum, start, end

We can implement this pseudocode in Python as follows:

def max_subarray_sum(arr): 
    # Get the length of the input array 
    l=len(arr) 
    # Initialize the running subarray sum and the maximum subarray sum to the first element in the array 
    max_sum = arr[0] 
    current_sum = arr[0] 
     
    # Initialize indices with 0 
    start = 0 
    end = 0 
    temp_start = 0 
    # Select an index of a subarray 
    for i in range(1,l): 
        # Get the sum of previous subarray elements and the current element 
        combined_sum  = current_sum + arr[i] 
 
        # If the current element is greater combined_sum, update current_sum to the current element, otherwise update it to combined_sum 
        if arr[i] > combined_sum : 
            current_sum= arr[i]  
            # Start the subarray at i 
            temp_start = i 
        else: 
            current_sum= combined_sum 
        # Update the maximum subarray sum 
        if current_sum>max_sum: 
            max_sum=current_sum 
            # Update the start and end indices of the subarray with the maximum sum 
            start = temp_start 
            end = i 
             
    return max_sum, start, end 
 
arr = [2, 3, -5, 6, -4] 
print("The input array is:",arr) 
result, start, end = max_subarray_sum(arr) 
print("The maximum subarray sum is:", result) 
print("The start and end indices of the subarray are:", (start,end)) 

Copy to clipboardCopy to clipboard

Output:

The input array is: [2, 3, -5, 6, -4] 
The maximum subarray sum is: 6 
The start and end indices of the subarray are: (0, 3) 

Copy to clipboardCopy to clipboard

You can implement this solution in Java and C++ to get a better understanding of how it works.

Conclusion

The maximum subarray sum problem is used in various use cases, such as stock price analysis to check the continuous sessions with the highest profit, and climate analysis to identify days with continuous warming or cooling. Kadane’s algorithm solves the maximum subarray problem in linear time, which helps us write optimal solutions for these use cases.

In this article, we discussed multiple solutions for the maximum subarray sum problem and implemented them in Java, C++, and Python. We also discussed finding the maximum subarray sum with the array indices. You can implement these solutions from scratch to better understand how the different solutions work.

To learn more about data structures and algorithms, you can take this course on data structures and algorithms with Python that discusses how to implement linked list, stack, queue, and hash map data structures. You might also like this advanced data structures and algorithms course with Python that discusses implementing doubly ended queues, binary search trees, string searching algorithms, and Hamiltonian algorithms in Python.

Frequently asked questions

1. Is Kadane’s algorithm greedy or DP?

Kadane’s algorithm is a dynamic programming algorithm. This is because we have two choices at every index: Either we include the current element in the previous subarray to get the maximum subarray sum, or we start a new subarray at the current index. However, Kadane’s algorithm finds the local maximum sum at each index in the array and derives the overall solution from the local maximums, which is a greedy approach. Hence, we sometimes term Kadane’s algorithm a greedy DP algorithm.

2. Is sliding window and Kadane’s algorithm the same?

No. The sliding window and Kadane’s algorithm are related but not the same algorithm. Kadane’s algorithm gives us the maximum sum of a contiguous subarray where the subarray length is not fixed. Using the sliding window technique, we solve problems involving fixed-length contiguous subarrays, like finding the max sum of any window of size k, where k is a given length.

3. Is Kadane’s algorithm asked in an interview?

Yes. Kadane’s algorithm is commonly asked in coding interviews for software engineering roles.

4. When to use Kadane’s algorithm?

We use Kadane’s algorithm to find the maximum sum of a contiguous subarray within a 1D array of integers.

5. What are the disadvantages of Kadane’s algorithm?

Kadane’s algorithm only gives the maximum subarray sum, not the indices. However, you can modify the implementation to get the start and end indices of the subarray with the maximum sum.

Codecademy Team

'The Codecademy Team, composed of experienced educators and tech experts, is dedicated to making tech skills accessible to all. We empower learners worldwide with expert-reviewed content that develops and enhances the technical skills needed to advance and succeed in their careers.'

Meet the full team

Learn more on Codecademy

Contents

What is the maximum subarray sum problem?
Find the maximum subarray sum using the brute-force approach
Find maximum subarray sum in O(n2) time
What is Kadane’s algorithm?
Find maximum subarray sum using Kadane’s algorithm in O(n) time
Find maximum subarray sum with array indices
Conclusion
Frequently asked questions

Kadane's Algorithm: Find Maximum Subarray Sum in an Array

What is the maximum subarray sum problem?

Learn Advanced Algorithms with Python: String Searching Algorithms

Find the maximum subarray sum using the brute-force approach

Find maximum subarray sum in O(n²) time

What is Kadane’s algorithm?

Find maximum subarray sum using Kadane’s algorithm in O(n) time

Python implementation

Java implementation

C++ implementation

Find maximum subarray sum with array indices

Conclusion

Frequently asked questions

1. Is Kadane’s algorithm greedy or DP?

2. Is sliding window and Kadane’s algorithm the same?

3. Is Kadane’s algorithm asked in an interview?

4. When to use Kadane’s algorithm?

5. What are the disadvantages of Kadane’s algorithm?

Related articles

Complete Guide to C++ Arrays

What is a for Loop in C++?

Prompt Engineering 101: Understanding Zero-Shot, One-Shot, and Few-Shot

Learn more on Codecademy

Learn Advanced Algorithms with Python: String Searching Algorithms

Learn Data Structures and Algorithms with Python

Learn Intermediate Java: Input and Output

Resources

Support

Resources

Support

Plans

Community

Subjects

Languages

Career building

Mobile

Mobile

Kadane's Algorithm: Find Maximum Subarray Sum in an Array

What is the maximum subarray sum problem?

Learn Advanced Algorithms with Python: String Searching Algorithms

Find the maximum subarray sum using the brute-force approach

Find maximum subarray sum in O(n2) time

What is Kadane’s algorithm?

Find maximum subarray sum using Kadane’s algorithm in O(n) time

Python implementation

Java implementation

C++ implementation

Find maximum subarray sum with array indices

Conclusion

Frequently asked questions

1. Is Kadane’s algorithm greedy or DP?

2. Is sliding window and Kadane’s algorithm the same?

3. Is Kadane’s algorithm asked in an interview?

4. When to use Kadane’s algorithm?

5. What are the disadvantages of Kadane’s algorithm?

Related articles

Complete Guide to C++ Arrays

What is a for Loop in C++?

Prompt Engineering 101: Understanding Zero-Shot, One-Shot, and Few-Shot

Learn more on Codecademy

Learn Advanced Algorithms with Python: String Searching Algorithms

Learn Data Structures and Algorithms with Python

Learn Intermediate Java: Input and Output

Find maximum subarray sum in O(n²) time