Kadane's Algorithm

Introduction

Kadane's Algorithm is an efficient dynamic programming approach designed to find the maximum sum of a contiguous subarray within a one-dimensional array of numbers. It elegantly solves a classic problem by iterating through the array just once, making it highly optimized for performance. This algorithm is a fundamental concept for mastering array-based optimization problems.

Quick Overview

Kadane's Algorithm efficiently finds the maximum sum of a contiguous subarray by iteratively updating a current maximum sum (ending at the current position) and a global maximum sum (overall best found so far).

Motivation

Consider the problem of finding the maximum sum of a contiguous subarray in an array of integers. A naive brute-force approach would involve checking every possible subarray, leading to O(N^3) complexity. Optimizing the sum calculation using prefix sums reduces this to O(N^2), but for large datasets, this is still too slow. We need an O(N) solution, which Kadane's Algorithm provides, making it suitable for competitive programming and real-world applications like financial analysis (e.g., identifying the most profitable stock trading period).

Core Idea

The algorithm maintains two key variables: current_max, which tracks the maximum sum of a contiguous subarray ending at the current position, and global_max, which stores the overall maximum sum found anywhere in the array so far. As it iterates through the array, for each element, it decides whether to extend the current_max subarray by adding the current element, or to start a brand new subarray from the current element if extending the previous one would result in a smaller sum.

Key Insight

The crucial insight is that if the sum of elements accumulated (current_max) up to a certain point becomes negative, that segment can never contribute positively to any maximum sum contiguous subarray that extends further to the right. Therefore, it is always optimal to discard that negative sum segment and start a new contiguous subarray from the current element, essentially 'resetting' current_max to the current element itself. This greedy decision at each step guarantees optimality.

Dry Run

Let's trace Kadane's Algorithm with the array nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4].

Initialize: global_max = -2, current_max = -2 (from nums[0])

1. i = 1, num = 1: current_max = max(1, -2 + 1) = max(1, -1) = 1 global_max = max(-2, 1) = 1 State: current_max = 1, global_max = 1

2. i = 2, num = -3: current_max = max(-3, 1 + (-3)) = max(-3, -2) = -2 global_max = max(1, -2) = 1 State: current_max = -2, global_max = 1

3. i = 3, num = 4: current_max = max(4, -2 + 4) = max(4, 2) = 4 global_max = max(1, 4) = 4 State: current_max = 4, global_max = 4

4. i = 4, num = -1: current_max = max(-1, 4 + (-1)) = max(-1, 3) = 3 global_max = max(4, 3) = 4 State: current_max = 3, global_max = 4

5. i = 5, num = 2: current_max = max(2, 3 + 2) = max(2, 5) = 5 global_max = max(4, 5) = 5 State: current_max = 5, global_max = 5

6. i = 6, num = 1: current_max = max(1, 5 + 1) = max(1, 6) = 6 global_max = max(5, 6) = 6 State: current_max = 6, global_max = 6

7. i = 7, num = -5: current_max = max(-5, 6 + (-5)) = max(-5, 1) = 1 global_max = max(6, 1) = 6 State: current_max = 1, global_max = 6

8. i = 8, num = 4: current_max = max(4, 1 + 4) = max(4, 5) = 5 global_max = max(6, 5) = 6 State: current_max = 5, global_max = 6

Final result: global_max = 6. The maximum sum contiguous subarray is [4, -1, 2, 1].

Algorithm

• Initialize global_max and current_max with the first element of the array.
• Iterate through the array starting from the second element (index 1).
• For each element num at the current index:
• a. Update current_max: current_max = max(num, current_max + num). This step determines whether to extend the current subarray or start a new one from num.
• b. Update global_max: global_max = max(global_max, current_max). This ensures global_max always holds the largest sum found so far.
• After iterating through all elements, global_max will contain the maximum sum of any contiguous subarray.

Pseudocode

function kadanesAlgorithm(nums):
    if nums is empty:
        return 0 // Or handle as an error based on problem constraints

    global_max = nums[0]
    current_max = nums[0]

    for i from 1 to nums.length - 1:
        // Calculate current_max: either extend the previous subarray or start new
        current_max = max(nums[i], current_max + nums[i])
        
        // Update global_max if current_max is greater
        global_max = max(global_max, current_max)

    return global_max

Code

(See Implementations block below)

Time Complexity

O(N) - The algorithm iterates through the input array exactly once. In each iteration, it performs a constant number of operations (one addition and two comparisons). Therefore, the total time taken is directly proportional to the number of elements N in the array, resulting in O(N) time complexity.

Space Complexity

O(1) - Kadane's algorithm uses a fixed, small number of variables (global_max, current_max, and a loop counter) regardless of the size of the input array. It does not require any additional data structures whose size scales with N, thus achieving O(1) auxiliary space complexity.

Advantages

• Optimal Time Complexity: Achieves O(N) time complexity, which is the best possible as every element must be examined at least once.
• Minimal Space Complexity: Requires only O(1) auxiliary space, making it extremely memory efficient.
• Simplicity: The algorithm is straightforward to understand and implement, making it a favorite in interviews.
• Foundation for Variations: Forms the basis for solving many other related problems (e.g., maximum sum circular subarray, maximum product subarray).

Limitations

• Contiguous Subarrays Only: Strictly designed to find the maximum sum for contiguous subarrays. It cannot be used if elements can be non-contiguous.
• Basic Form Does Not Return Indices: The standard implementation only returns the maximum sum. Extending it to return the start and end indices of the subarray requires minor modifications to track these during iteration.
• Not for Fixed Length Subarrays: If a maximum sum subarray of a fixed length K is required, a sliding window approach is generally more direct and efficient.
• Not Directly Applicable to 2D: For 2D matrices, Kadane's algorithm is applied iteratively on rows/columns, but it's not a direct, single-pass solution for the entire matrix.

Common Mistakes

• Incorrect Initialization: A common error is initializing global_max or current_max to 0. If all numbers in the array are negative, this would incorrectly return 0 instead of the largest single negative number. Always initialize with nums[0] and start the loop from i=1.
• Off-by-one Errors: Incorrect loop bounds, especially when initializing with nums[0] and then iterating from index 1. Ensure the loop covers all remaining elements correctly.
• Confusing global_max and current_max: Misunderstanding when to update each or assigning current_max to global_max prematurely can lead to incorrect results.
• Handling Empty Arrays: Not considering the edge case of an empty input array can lead to index out-of-bounds errors. While many competitive programming problems guarantee non-empty arrays, robust code should handle this explicitly.

Edge Cases

• Single Element Array: nums = [5] -> global_max = 5. The algorithm must correctly return the element itself.
• All Positive Numbers: nums = [1, 2, 3] -> global_max = 6. The algorithm should correctly sum all elements.
• All Negative Numbers: nums = [-2, -1, -3] -> global_max = -1. The algorithm must correctly identify the largest single negative number as the maximum sum contiguous subarray.
• Mixed Positive and Negative Numbers: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] -> global_max = 6. This is the typical use case that validates the algorithm's core logic.
• Empty Array: Depending on problem constraints, either return 0, throw an error, or assume the input array is never empty.

Recognition Tricks

• Keywords: Look for phrases like 'maximum/minimum subarray sum', 'largest sum subarray', 'contiguous subarray', or 'subsegment with greatest sum'.
• Problem Transformation: Problems where an array can be transformed (e.g., creating a difference array from a profit/loss sequence) into a form solvable by Kadane's algorithm.
• O(N) Requirement: If an O(N^2) or O(N^3) brute-force solution is clearly too slow given the input constraints (e.g., N up to 10^5 or 10^6), Kadane's is a prime candidate for array sum problems.
• Greedy Choice at Each Step: The possibility of making an optimal local choice (extend or restart subarray) that leads to a global optimum is a strong indicator.

When To Use

• When the problem explicitly asks for the maximum sum of a contiguous subarray in a one-dimensional array.
• When a problem can be converted into finding the maximum contiguous subarray sum (e.g., 'Best Time to Buy and Sell Stock' can be viewed as finding the max subarray sum of daily price differences).
• As a foundational building block for more complex problems, such as finding the maximum sum of a contiguous subarray in a circular array (which involves two applications of Kadane's).
• When an O(N) time complexity is mandatory for array sum problems where the contiguity of elements is important.

Alternative Approaches

• Brute Force (O(N^3)): Iterate through all possible start indices i, then all possible end indices j, and then sum elements from i to j. Highly inefficient.
• Optimized Brute Force with Prefix Sums (O(N^2)): Precompute prefix sums in O(N). Then, for every pair of (i, j), calculate sum(i, j) in O(1) using prefix sums. This reduces the complexity but is still quadratic.
• Divide and Conquer (O(N log N)): Recursively divide the array into two halves. Find the maximum subarray sum in the left half, in the right half, and a third case: the maximum sum subarray that crosses the midpoint. This is a valid approach but typically more complex and less efficient than Kadane's in terms of constant factors.
• Dynamic Programming (Implicitly Kadane's): Kadane's algorithm itself is a form of dynamic programming where dp[i] (equivalent to current_max) represents the maximum subarray sum ending at index i. The recurrence relation is dp[i] = max(nums[i], dp[i-1] + nums[i]).

Interview Perspective

Kadane's Algorithm is a staple in coding interviews, serving as a gateway to dynamic programming and array optimization. Interviewers use it to assess a candidate's ability to identify optimal substructure, formulate a greedy strategy, and handle edge cases. Expect direct questions on finding the maximum subarray sum, or variations like finding the actual start/end indices of the subarray, maximum product subarray, or maximum sum circular subarray. It's also a common precursor to problems involving 2D arrays (e.g., maximum sum rectangle) where Kadane's can be applied to rows/columns. Demonstrating an O(N) solution quickly, explaining the intuition (especially the 'reset' logic), and discussing its time/space complexity are crucial for a strong performance.

Key Takeaways

• Kadane's Algorithm is a powerful, greedy dynamic programming approach for the maximum contiguous subarray sum problem.
• The core idea: current_max = max(current_element, current_element + previous_current_max).
• The 'reset' logic: if current_max becomes negative, it's optimal to discard it and start a new subarray from the current element.
• It provides an optimal O(N) time and O(1) space solution, making it highly efficient.
• Essential for recognizing and solving various contiguous subarray sum problems, including those disguised by transformations.
• Always consider and correctly handle edge cases: empty arrays, single elements, and arrays composed entirely of negative numbers.

Practice Problems

(See Practice Problems index below)

#include <vector>
#include <algorithm>

class Solution {
public:
    int maxSubArray(std::vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }

        int globalMax = nums[0];
        int currentMax = nums[0];

        for (size_t i = 1; i < nums.size(); ++i) {
            currentMax = std::max(nums[i], currentMax + nums[i]);
            globalMax = std::max(globalMax, currentMax);
        }

        return globalMax;
    }
};