Common Array Patterns - Learning Module

Loading content...

0/276

Kadane's Algorithm Intuition — Maximum Subarray

The Maximum Subarray Problem

Consider a stock trader analyzing daily profit and loss figures: [+5, -2, +3, -1, +4, -6, +2, +1]. Some days are profitable, others not. The trader wants to know: "What's the maximum profit I could have made by trading in some contiguous period?"

This is the Maximum Subarray Problem—one of the most famous problems in computer science. Given an array of numbers (possibly negative), find the contiguous subarray with the largest sum.

The problem appears everywhere:

Financial analysis: Best window for trading or investment
Signal processing: Finding the strongest continuous signal
Bioinformatics: Identifying regions of high activity in gene sequences
Weather patterns: Detecting periods of temperature anomalies
Performance monitoring: Finding peak usage windows

What You Will Master

By the end of this page, you will deeply understand Kadane's algorithm: the intuition behind it, why greedy/DP thinking leads to an O(n) solution, the mathematical invariants that make it work, edge case handling, and variations that appear in real problems.

Formalizing the Problem

Problem Statement:

Given an integer array nums of length n, find the contiguous subarray (containing at least one element) which has the largest sum, and return that sum.

Examples:

Input:  [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] has the largest sum = 6

Input:  [1]
Output: 1

Input:  [5, 4, -1, 7, 8]
Output: 23 (entire array)

Input:  [-1, -2, -3, -4]
Output: -1 (least negative element)

Key Constraint

The subarray must contain at least one element. This matters when all elements are negative—we can't return 0 (empty subarray). We must return the maximum single element, which will be the least negative.

Why is this problem interesting?

At first glance, it seems you'd need to check all possible subarrays to find the maximum. But there are O(n²) subarrays in an array of length n—and computing the sum of each takes O(n) time in the naive case, leading to O(n³) complexity.

With prefix sums (from Page 1), we can improve to O(n²)—compute all subarray sums in constant time each. But can we do better?

Kadane's algorithm answers with an emphatic yes: O(n) time, O(1) space. This is optimal—we can't do better than linear time since we must examine every element at least once.

Naive Approaches and Their Limitations

Before appreciating Kadane's elegance, let's understand why straightforward approaches fail at scale.

naiveMaxSubarray.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
 * Brute Force: Check every possible subarray
 * Time: O(n³) — n² subarrays, O(n) to sum each
 */
function maxSubarrayBruteForce(nums: number[]): number {
    let maxSum = -Infinity;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i; j < n; j++) {
            // Sum subarray from i to j
            let sum = 0;
            for (let k = i; k <= j; k++) {
                sum += nums[k];
            }
            maxSum = Math.max(maxSum, sum);
        }
    }
    
    return maxSum;
}
 
/**
 * Optimized Brute Force: Remove inner loop
 * Time: O(n²) — maintain running sum while extending right boundary
 */
function maxSubarrayOptimized(nums: number[]): number {
    let maxSum = -Infinity;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        let currentSum = 0;
        for (let j = i; j < n; j++) {
            currentSum += nums[j];
            maxSum = Math.max(maxSum, currentSum);
        }
    }
    
    return maxSum;
}

Complexity Comparison
Approach	Time	Space	1K elements	1M elements
Brute Force	O(n³)	O(1)	1 billion ops	10¹⁸ ops
Optimized Brute Force	O(n²)	O(1)	1 million ops	10¹² ops
With Prefix Sums	O(n²)	O(n)	1 million ops	10¹² ops
Kadane's Algorithm	O(n)	O(1)	1 thousand ops	1 million ops

The jump from O(n²) to O(n) is not incremental—it's transformative. At 1 million elements, we go from waiting hours to completing in milliseconds. This is why algorithmic thinking matters: the right approach doesn't just improve performance, it changes what's computationally possible.

The Key Insight: Local Decisions, Global Optimum

Kadane's algorithm works because of a beautiful structural property: the optimal subarray ending at position i can be computed from the optimal subarray ending at position i-1.

This is the essence of dynamic programming: breaking a problem into overlapping subproblems where the solution to each subproblem informs the next.

The Central Question at Each Position:

As we scan through the array, at each index i we face a decision:

Extend: Add nums[i] to the best subarray ending at i-1
Start fresh: Begin a new subarray starting at i

The choice depends on whether the previous subarray sum is helping or hurting us.

The Decision Rule

If the best subarray sum ending at position i-1 is negative, it can only drag down any subarray we extend. We're better off starting fresh at i. If it's positive (or zero), extending is beneficial.

Formal Recurrence:

Let maxEndingHere[i] = maximum sum of any subarray ending exactly at index i.

maxEndingHere[0] = nums[0]
maxEndingHere[i] = max(nums[i], maxEndingHere[i-1] + nums[i])

The answer is the maximum value of maxEndingHere[i] across all i:

result = max(maxEndingHere[0], maxEndingHere[1], ..., maxEndingHere[n-1])

Why This Works:

Every contiguous subarray ends somewhere. By computing the best subarray ending at each position, we're guaranteed to find the global maximum. And because each position's answer depends only on the previous position, we need just one pass and O(1) space.

kadaneExplained.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 * Kadane's Algorithm — Step-by-step trace
 * 
 * Array: [-2, 1, -3, 4, -1, 2, 1, -5, 4]
 * 
 * i=0: nums[0]=-2
 *      maxEndingHere = max(-2, 0 + -2) = -2
 *      (Actually, for i=0, it's just nums[0])
 *      globalMax = -2
 * 
 * i=1: nums[1]=1
 *      Previous maxEndingHere = -2 (negative, hurts us)
 *      maxEndingHere = max(1, -2 + 1) = max(1, -1) = 1
 *      (Start fresh is better)
 *      globalMax = max(-2, 1) = 1
 * 
 * i=2: nums[2]=-3
 *      Previous maxEndingHere = 1 (positive, helps us)
 *      maxEndingHere = max(-3, 1 + -3) = max(-3, -2) = -2
 *      (Extending is better than starting with -3 alone)
 *      globalMax = max(1, -2) = 1
 * 
 * i=3: nums[3]=4
 *      Previous maxEndingHere = -2 (negative, hurts us)
 *      maxEndingHere = max(4, -2 + 4) = max(4, 2) = 4
 *      (Start fresh is better)
 *      globalMax = max(1, 4) = 4
 * 
 * i=4: nums[4]=-1
 *      Previous maxEndingHere = 4 (positive, helps us)
 *      maxEndingHere = max(-1, 4 + -1) = max(-1, 3) = 3
 *      globalMax = max(4, 3) = 4
 * 
 * i=5: nums[5]=2
 *      Previous maxEndingHere = 3 (positive, helps us)
 *      maxEndingHere = max(2, 3 + 2) = max(2, 5) = 5
 *      globalMax = max(4, 5) = 5
 * 
 * i=6: nums[6]=1
 *      Previous maxEndingHere = 5 (positive, helps us)
 *      maxEndingHere = max(1, 5 + 1) = max(1, 6) = 6
 *      globalMax = max(5, 6) = 6
 * 
 * i=7: nums[7]=-5
 *      Previous maxEndingHere = 6 (positive, helps us)
 *      maxEndingHere = max(-5, 6 + -5) = max(-5, 1) = 1
 *      globalMax = max(6, 1) = 6
 * 
 * i=8: nums[8]=4
 *      Previous maxEndingHere = 1 (positive, helps us)
 *      maxEndingHere = max(4, 1 + 4) = max(4, 5) = 5
 *      globalMax = max(6, 5) = 6
 * 
 * Final Answer: 6 (subarray [4, -1, 2, 1])
 */

Kadane's Algorithm: Implementation

The beauty of Kadane's algorithm is how simple the final code becomes—a testament to the power of clear thinking leading to clean implementation:

kadane.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * Kadane's Algorithm — Maximum Subarray Sum
 * 
 * Time Complexity:  O(n) — single pass through the array
 * Space Complexity: O(1) — only two variables regardless of input size
 * 
 * @param nums Array of integers (can include negatives)
 * @returns Maximum sum of any contiguous subarray
 */
function maxSubArray(nums: number[]): number {
    // Edge case: empty array
    if (nums.length === 0) {
        throw new Error("Array must contain at least one element");
    }
    
    // Initialize with first element
    let maxEndingHere = nums[0];  // Best subarray ending at current position
    let maxSoFar = nums[0];       // Best subarray seen anywhere so far
    
    // Process remaining elements
    for (let i = 1; i < nums.length; i++) {
        // Decision: extend previous subarray or start fresh?
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        
        // Update global maximum if current ending is better
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    
    return maxSoFar;
}
 
// Test cases
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([1]));                               // 1
console.log(maxSubArray([5, 4, -1, 7, 8]));                  // 23
console.log(maxSubArray([-1, -2, -3, -4]));                  // -1

Alternative Formulation:

The same logic expressed differently—some find this version clearer:

kadaneAlternative.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Alternative formulation: reset when sum goes negative
 */
function maxSubArrayAlt(nums: number[]): number {
    let maxSum = nums[0];
    let currentSum = 0;
    
    for (const num of nums) {
        // If current sum is negative, start fresh
        if (currentSum < 0) {
            currentSum = 0;
        }
        
        currentSum += num;
        maxSum = Math.max(maxSum, currentSum);
    }
    
    return maxSum;
}

Equivalent Formulations

Both versions implement the same logic: abandon a negative sum because it can only hurt future subarrays. The first version makes the max() decision explicit; the second resets to 0 before adding the new element. Choose whichever resonates with your mental model.

Finding the Actual Subarray

The basic algorithm returns only the maximum sum. Often, we also need to know which subarray achieves that sum. This requires tracking the start and end indices:

kadaneWithIndices.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Kadane's Algorithm with subarray tracking.
 * Returns both the maximum sum and the subarray that achieves it.
 */
interface MaxSubarrayResult {
    maxSum: number;
    startIndex: number;
    endIndex: number;
    subarray: number[];
}
 
function maxSubArrayWithIndices(nums: number[]): MaxSubarrayResult {
    if (nums.length === 0) {
        throw new Error("Array must contain at least one element");
    }
    
    let maxEndingHere = nums[0];
    let maxSoFar = nums[0];
    
    // Track indices of current subarray and best subarray
    let currentStart = 0;
    let bestStart = 0;
    let bestEnd = 0;
    
    for (let i = 1; i < nums.length; i++) {
        // Decision: extend or start fresh?
        if (nums[i] > maxEndingHere + nums[i]) {
            // Start fresh: new subarray begins at i
            maxEndingHere = nums[i];
            currentStart = i;
        } else {
            // Extend: continue from previous
            maxEndingHere = maxEndingHere + nums[i];
        }
        
        // Update global best if current ending is better
        if (maxEndingHere > maxSoFar) {
            maxSoFar = maxEndingHere;
            bestStart = currentStart;
            bestEnd = i;
        }
    }
    
    return {
        maxSum: maxSoFar,
        startIndex: bestStart,
        endIndex: bestEnd,
        subarray: nums.slice(bestStart, bestEnd + 1)
    };
}
 
// Example
const result = maxSubArrayWithIndices([-2, 1, -3, 4, -1, 2, 1, -5, 4]);
console.log(result);
// {
//   maxSum: 6,
//   startIndex: 3,
//   endIndex: 6,
//   subarray: [4, -1, 2, 1]
// }

Edge Case: Multiple Subarrays with Same Sum

If multiple subarrays share the maximum sum, this implementation returns the first one found (leftmost). Depending on requirements, you might want the shortest, longest, or all such subarrays—adjust the comparison logic accordingly.

Variations and Extensions

The core idea of Kadane's algorithm extends to many related problems. Here are important variations:

Variation 1: Minimum Subarray Sum

•Problem: Find the contiguous subarray with the minimum sum.
•Solution: Either negate all elements and apply Kadane's, or flip the max/extension logic.
•Application: Finding the worst-performing period, maximum loss intervals.

minSubarray.ts
1
2
3
4
5
6
7
8
9
10
11
12
// Minimum subarray sum — mirror of Kadane's
function minSubArray(nums: number[]): number {
    let minEndingHere = nums[0];
    let minSoFar = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        minEndingHere = Math.min(nums[i], minEndingHere + nums[i]);
        minSoFar = Math.min(minSoFar, minEndingHere);
    }
    
    return minSoFar;
}

Variation 2: Maximum Subarray Product

•Problem: Find the contiguous subarray with the maximum product.
•Complication: Negative numbers can flip sign—a large negative times another negative becomes positive.
•Solution: Track both maximum and minimum products ending at each position. The minimum might become maximum after multiplying by a negative.

maxProduct.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Maximum Product Subarray
 * 
 * Key insight: We track both max and min because:
 * - A current negative × previous min (negative) = large positive
 * - The min might become the new max after a sign flip
 */
function maxProduct(nums: number[]): number {
    let maxProd = nums[0];
    let minProd = nums[0];
    let result = nums[0];
    
    for (let i = 1; i < nums.length; i++) {
        const num = nums[i];
        
        // Current number might swap max and min if negative
        const tempMax = Math.max(
            num,
            maxProd * num,
            minProd * num
        );
        const tempMin = Math.min(
            num,
            maxProd * num,
            minProd * num
        );
        
        maxProd = tempMax;
        minProd = tempMin;
        
        result = Math.max(result, maxProd);
    }
    
    return result;
}
 
console.log(maxProduct([2, 3, -2, 4]));    // 6  ([2,3])
console.log(maxProduct([-2, 0, -1]));      // 0  (single 0)
console.log(maxProduct([-2, -3, -4]));     // 12 ([-2,-3] or [-3,-4])

Variation 3: Maximum Circular Subarray Sum

•Problem: The array is circular—subarrays can wrap around from end to beginning.
•Insight: A wrapping subarray is the total sum minus a non-wrapping subarray in the middle.
•Solution: max(normal Kadane's, total_sum - min_subarray_sum).
•Edge case: When all elements are negative, the circular case gives 0 (empty subarray), which is invalid. Handle specially.

circularMaxSubarray.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/**
 * Maximum Circular Subarray Sum
 * 
 * Key insight: Wrapping around = taking from both ends
 *            = total_sum - (sum of middle part we skip)
 *            
 * So maximum wrap-around sum = total_sum - minimum subarray sum
 * 
 * Answer = max(normal_max, total - min_subarray)
 */
function maxSubarrayCircular(nums: number[]): number {
    let totalSum = 0;
    
    let maxSum = nums[0];
    let currentMax = nums[0];
    
    let minSum = nums[0];
    let currentMin = nums[0];
    
    for (let i = 0; i < nums.length; i++) {
        totalSum += nums[i];
        
        if (i > 0) {
            currentMax = Math.max(nums[i], currentMax + nums[i]);
            maxSum = Math.max(maxSum, currentMax);
            
            currentMin = Math.min(nums[i], currentMin + nums[i]);
            minSum = Math.min(minSum, currentMin);
        }
    }
    
    // If all elements are negative, totalSum - minSum = 0 (empty)
    // In that case, we must return the normal max (least negative)
    if (maxSum < 0) {
        return maxSum;
    }
    
    return Math.max(maxSum, totalSum - minSum);
}
 
console.log(maxSubarrayCircular([1, -2, 3, -2]));      // 3
console.log(maxSubarrayCircular([5, -3, 5]));          // 10 (wraps)
console.log(maxSubarrayCircular([-3, -2, -3]));        // -2

Why Greedy/DP Works Here

Kadane's algorithm feels almost too simple. Why does a single pass with local decisions guarantee a global optimum? Understanding this requires recognizing the problem's optimal substructure and greedy choice property.

Optimal Substructure

The maximum subarray ending at position i either: (a) is just the element at i, or (b) is the maximum subarray ending at i-1 extended by element i. There's no third option. This is optimal substructure—optimal solutions contain optimal solutions to subproblems.

Proof of Correctness:

Let's prove that Kadane's algorithm always finds the maximum subarray sum.

Claim: At each iteration i, maxEndingHere equals the maximum sum of any subarray ending exactly at index i.

Base Case (i=0):

The only subarray ending at index 0 is [nums[0]].
We initialize maxEndingHere = nums[0]. ✓

Inductive Step:

Assume maxEndingHere correctly stores the maximum sum ending at i-1.

Any subarray ending at i either:

Starts at i (sum = nums[i]), or
Extends a subarray ending at i-1 (sum = maxEndingHere + nums[i])

By taking max(nums[i], maxEndingHere + nums[i]), we correctly compute the maximum sum ending at i.

Conclusion: Since we track maxSoFar as the maximum of all maxEndingHere values, and every subarray ends somewhere, we're guaranteed to find the global maximum.

DP vs Greedy Classification

Kadane's algorithm is often classified as both dynamic programming (it uses recurrence: f(i) depends on f(i-1)) and greedy (each step makes a locally optimal choice). This overlap occurs because the greedy choice here is provably optimal for the subproblem structure.

Alternative: Divide and Conquer

Before Kadane's algorithm became the standard, the divide and conquer approach was common. While asymptotically slower (O(n log n)), it's instructive for understanding problem decomposition and appears in some interview contexts.

The Approach:

Divide the array into two halves
The maximum subarray is either:
- Entirely in the left half
- Entirely in the right half
- Crosses the midpoint (includes elements from both halves)
Recursively solve for left and right halves
Compute the maximum crossing subarray in O(n)
Return the maximum of the three cases

divideAndConquer.ts
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
/**
 * Divide and Conquer approach to Maximum Subarray
 * Time: O(n log n), Space: O(log n) for recursion stack
 */
function maxSubArrayDC(nums: number[]): number {
    return maxSubArrayHelper(nums, 0, nums.length - 1);
}
 
function maxSubArrayHelper(nums: number[], left: number, right: number): number {
    // Base case: single element
    if (left === right) {
        return nums[left];
    }
    
    const mid = Math.floor((left + right) / 2);
    
    // Maximum in left half
    const leftMax = maxSubArrayHelper(nums, left, mid);
    
    // Maximum in right half
    const rightMax = maxSubArrayHelper(nums, mid + 1, right);
    
    // Maximum crossing the midpoint
    const crossMax = maxCrossingSubarray(nums, left, mid, right);
    
    return Math.max(leftMax, rightMax, crossMax);
}
 
function maxCrossingSubarray(
    nums: number[],
    left: number,
    mid: number,
    right: number
): number {
    // Find max sum going left from mid
    let leftSum = -Infinity;
    let sum = 0;
    for (let i = mid; i >= left; i--) {
        sum += nums[i];
        leftSum = Math.max(leftSum, sum);
    }
    
    // Find max sum going right from mid+1
    let rightSum = -Infinity;
    sum = 0;
    for (let i = mid + 1; i <= right; i++) {
        sum += nums[i];
        rightSum = Math.max(rightSum, sum);
    }
    
    return leftSum + rightSum;
}

Kadane's vs Divide & Conquer
Metric	Kadane's	Divide & Conquer
Time Complexity	O(n)	O(n log n)
Space Complexity	O(1)	O(log n)
Implementation	Simpler	More complex
Cache Locality	Excellent	Poor (jumping around)
Parallelization	Hard	Natural

When D&C Makes Sense

Divide and conquer is rarely preferred for maximum subarray. However, it parallelizes well—the left and right subproblems are independent. In distributed computing scenarios where data is already partitioned, D&C may be more practical despite higher complexity.

Summary: Kadane's Algorithm

Kadane's algorithm is a masterclass in algorithmic elegance—taking a problem that appears to require O(n²) or O(n³) time and solving it in linear time with constant space. Let's consolidate the key insights:

Key Takeaways

•The core insight: At each position, decide whether to extend the previous subarray or start fresh. A negative running sum can only hurt future extensions.
•The recurrence: maxEndingHere[i] = max(nums[i], maxEndingHere[i-1] + nums[i]). The global max is the best maxEndingHere across all positions.
•O(n) time, O(1) space: Single pass, two variables. Optimal and elegant.
•Variations abound: Minimum subarray, maximum product, circular arrays, and more—all use similar reasoning with adjustments.
•Greedy works because of structure: Optimal substructure means local decisions lead to global optima.
•Index tracking is straightforward: Record where you start fresh and when you update the global best.

What's Next:

With prefix sums and Kadane's algorithm mastered, you have powerful tools for aggregate and contiguous range computations. In the next page, we explore array rotation and reversal—fundamental transformations that appear in countless problems and form the basis for more complex in-place algorithms.

Pattern Acquired

Kadane's algorithm is now part of your permanent toolkit. Whenever you see 'maximum/minimum contiguous subarray,' you should immediately think of this approach. The technique demonstrates how clean problem decomposition leads to remarkably simple solutions.