Course contentsShow
← Computer Science
Lesson 258 of 2,8726. Arrays and Basic CollectionsFree lesson

Kadane's Algorithm: Maximum Subarray Sum

Find contiguous subarray with largest sum using dynamic programming approach in O(n) time with O(1) space.

Kadane's Algorithm: Maximum Subarray Sum

You'll learn how to find the largest possible sum of consecutive elements in an array using a clever single-pass technique.

The Problem

Imagine you have an array of numbers (both positive and negative), and you need to find which continuous slice of elements adds up to the biggest sum. For example, in [-2, 1, -3, 4, -1, 2, 1, -5, 4], the best subarray is [4, -1, 2, 1] with sum 6.

A brute-force approach checking every possible subarray would be slow. Kadane's Algorithm solves this in O(n) time using just O(1) extra space.

The Core Idea

Think of walking through the array, carrying a running sum. At each step, you make a choice: either add the current element to your existing sum, or start fresh from this element. Why start fresh? Because if your running sum has become negative, it's dragging you down—better to abandon it.

Meanwhile, track the best (maximum) sum you've seen so far.

How It Works

def max_subarray_sum(arr):
    max_sum = arr[0]
    current_sum = arr[0]
    
    for i in range(1, len(arr)):
        # Either extend current subarray or start new
        current_sum = max(arr[i], current_sum + arr[i])
        # Update best result seen so far
        max_sum = max(max_sum, current_sum)
    
    return max_sum

At each element, current_sum represents the best subarray ending at this position. We either continue the previous subarray or start anew.

The Analogy

It's like climbing hills: if you're in a valley (negative sum), sometimes it's better to restart your climb from the next position rather than dragging that deficit forward.

Key Takeaway: Kadane's Algorithm finds the maximum subarray sum in one pass by maintaining the best sum ending at each position, deciding at each step whether to extend or restart, achieving O(n) time with O(1) space.