Find Maximum Subarray Sum using Kadane's Algorithm - Optimal Solution

Arrays

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

Given an array of integers (which may include negative numbers), your task is to find the maximum sum of any contiguous subarray.

This problem is also known as the Maximum Subarray Problem.

  • You must return the maximum sum possible by choosing a continuous range of elements from the array.
  • If the array is empty, return 0.

Use Kadane's Algorithm to solve it efficiently in linear time.

Examples❯

Input Array Maximum Subarray Sum Description
[1, 2, 3, 4] 10 Whole array has positive values, total sum is the maximumVisualization
[-2, 1, -3, 4, -1, 2, 1, -5, 4] 6 Maximum sum from subarray [4, -1, 2, 1]Visualization
[-1, -2, -3, -4] -1 All elements are negative; single largest number is the answerVisualization
[5] 5 Single element array, subarray is the element itselfVisualization
[0, 0, 0] 0 All elements are zero, so the max subarray sum is 0Visualization
[] 0 Empty array returns 0 by default (no elements to sum)Visualization
[-2, -1, 0, -3] 0 Zero is the maximum subarray sumVisualization

Solution❯

Step-by-Step Solution to Maximum Subarray Sum Problem

Understanding the Problem

We are given an array of integers. Our task is to find the maximum sum of a contiguous subarray. That means we must select a subarray (a sequence of elements that appear consecutively) such that the sum of its elements is as large as possible.

We’ll explore this problem step-by-step using examples, and then apply a proven technique called Kadane’s Algorithm to solve it efficiently.

Let's Begin with an Example

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

We need to find a contiguous subarray that gives the highest sum. Visually exploring this array, we notice that the subarray [4, -1, 2, 1] adds up to 6, which is the maximum possible sum of any contiguous subarray in this case.

Step-by-Step Approach

We start scanning the array from left to right, keeping track of two variables:

  • currentSum: The sum of the current subarray being considered
  • maxSum: The highest sum found so far

At each element, we decide:

  • Should we include this element in the current subarray?
  • Or start a new subarray starting from this element?

This decision is made by taking the maximum of:

currentSum = max(current element, currentSum + current element)

And then we update:

maxSum = max(maxSum, currentSum)

Intuition for Beginners

If the previous sum is helping us grow (i.e., it's positive), we add the current number to it. But if the previous sum is dragging us down (i.e., it’s negative), we just start fresh from the current number. We always keep track of the maximum we've seen so far.

Understanding Edge Cases

1. All Positive Numbers

Input: [1, 2, 3, 4]
Every number is good for the sum, so we take the whole array. Result = 10

2. All Negative Numbers

Input: [-3, -2, -1]
All sums are negative, so the least negative (i.e., closest to zero) single number is the best. Result = -1

3. Mixed Positive and Negative

Input: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Kadane’s Algorithm picks [4, -1, 2, 1] as the best subarray. Result = 6

4. Zeros or Zero as Maximum

Input: [0, 0, 0] or [-2, -1, 0, -3]
Sometimes zero is the best possible sum, especially when no positive numbers exist. Result = 0

5. Single Element Array

Input: [5] or [-4]
The only element is the result. Result = the element itself

6. Empty Array

Input: []
There are no elements to consider. By convention, the result is 0 or may be undefined depending on the context.

Why Kadane’s Algorithm Works So Well

Instead of trying all possible subarrays (which takes O(n²) time), Kadane’s Algorithm goes through the array just once – that’s O(n) time!

It continuously maintains the best sum seen so far and handles all types of arrays—positive, negative, mixed, zero, or even empty. That's why it's one of the most elegant algorithms in dynamic programming!

Algorithm Steps❯

  1. Given an integer array arr.
  2. Initialize two variables: max_sum and current_sum with the value of the first element.
  3. Iterate through the array starting from index 1.
  4. At each step, update current_sum as the maximum of the current element or current_sum + current_element.
  5. Update max_sum if current_sum is greater than max_sum.
  6. After the loop, return max_sum as the result.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#include <stdio.h>

int maxSubarraySum(int arr[], int n) {
    int maxSum = arr[0], currentSum = arr[0];
    for (int i = 1; i < n; i++) {
        currentSum = (currentSum + arr[i] > arr[i]) ? currentSum + arr[i] : arr[i];
        maxSum = (maxSum > currentSum) ? maxSum : currentSum;
    }
    return maxSum;
}

int main() {
    int arr[] = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    printf("Maximum Subarray Sum: %d\n", maxSubarraySum(arr, n));
    return 0;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(n)Even in the best case, Kadane's Algorithm must iterate through all elements of the array to compute the maximum subarray sum.
Average CaseO(n)Kadane's Algorithm processes each element once, maintaining a running sum and updating the maximum found so far in linear time.
Worst CaseO(n)In all cases—whether the array has all negative values, all positives, or a mix—Kadane's algorithm completes in linear time by scanning the entire array.

Space Complexity❯

O(1)

Explanation: Kadane's Algorithm uses only constant space with a few variables (max_sum and current_sum) to track the state—no extra arrays or recursion are used.


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...