ReviseAlgo Logo

Arrays

Kadane's Algorithm

Find the maximum sum contiguous subarray in O(N) linear time and O(1) space using dynamic programming local vs global optimization.

Last Updated: August 2, 2026 • 20 min read

1. Introduction

What is Kadane's Algorithm?

Kadane's Algorithm is an elegant dynamic programming algorithm used to find the maximum sum of a contiguous subarray within a 1D array of numbers.

Why is it Important?

A brute-force solution checking all O(N²) contiguous subarrays takes O(N³) or O(N²) time. Kadane's algorithm solves this in a single pass taking O(N) linear time and O(1) space complexity.

Where is it Used?

  • Financial Stock Analysis: Finding the optimal consecutive holding period to maximize profit.
  • Genomics & Bioinformatics: Identifying high-density coding regions (GC-rich segments) in DNA sequences.

    • 2. Mental Model

    Imagine walking along a path collecting coins (+ numbers) and paying toll fees (- numbers).

    At each step, you ask yourself:

    "Is my current accumulated money actually helping me, or is it negative baggage that hurts my future total?"

    If your accumulated balance drops below zero, throw it away! Reset your wallet to 0 and start collecting fresh from the current position. Carrying negative debt into future steps only reduces your potential maximum sum.

    3. Concept: The Core Recurrence Relation

    At index i, the maximum sum of a subarray ending at index i is:

    currentMax[i] = \max(nums[i], \, currentMax[i - 1] + nums[i])
    globalMax = \max(globalMax, \, currentMax[i])

    Maximum Circular Subarray Sum Variant

    4. Visuals

    Step-by-Step Trace Matrix for [-2, 1, -3, 4, -1, 2, 1, -5, 4]

    Trace Table

    Index inums[i]Choice: max(nums[i], cur + nums[i])currentMaxglobalMax
    0-2Start baseline-2-2
    11\max(1, -2 + 1) = 11 (Reset)1
    2-3\max(-3, 1 - 3) = -2-21
    34\max(4, -2 + 4) = 44 (Reset)4
    4-1\max(-1, 4 - 1) = 334
    52\max(2, 3 + 2) = 555
    61\max(1, 5 + 1) = 666
    7-5\max(-5, 6 - 5) = 116
    84\max(4, 1 + 4) = 556

    5. Real-World Examples

  • Signal Spike Analysis: Detecting peak burst activity periods in network latency metrics or sound intensity wave data.
  • Algorithmic Trading Strategies: Calculating the maximum drawdown or maximum growth window for asset prices.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers often ask: "Find the contiguous subarray with the largest sum and return its sum (or its actual subarray elements)."

    Common Mistakes

    Warning: 1. Initializing globalMax = 0: If all elements in the input array are negative (e.g., [-5, -2, -8]), initializing globalMax = 0 returns 0 instead of the correct answer -2. Always initialize globalMax = nums[0].
    > 2. Confusing Subarray with Subsequence: Subarrays MUST be contiguous. If non-contiguous elements are allowed, it's a Subsequence problem (solved via standard DP or greedy sorting).

    7. Summary

  • Core Rule: At each step, either extend the running sum or start fresh: cur = max(num, cur + num).
  • Initialization: Always set currentMax = nums[0] and globalMax = nums[0] to handle negative arrays.
  • Space & Time: Solves maximum subarray sum in O(N) time and O(1) auxiliary space.

    • 8. Quiz

    Question 1: What does Kadane's algorithm return for the array [-5, -3, -8, -1, -4]? Answer: -1 (the maximum single negative element).
    Question 2: What condition causes Kadane's algorithm to discard the current running sum and start fresh? Answer: When currentMax + nums[i] < nums[i], which happens whenever currentMax < 0 (the previous accumulated sum was negative).
    Question 3: How do you solve Maximum Sum Subarray in a CIRCULAR array? Answer: The answer is \max(Kadane(nums), \, TotalSum - MinimumSubarraySum(nums)), provided not all numbers are negative.
    Question 4: What is the space complexity of Kadane's Algorithm? Answer: O(1) space because it only uses two scalar variables (currentMax and globalMax).
    Question 5: Can Kadane's Algorithm be extended to 2D matrices (Maximum Sum Submatrix)? Answer: Yes! By fixing top and bottom row boundaries and using 1D Kadane on column sums, a 2D submatrix max sum can be found in O(Rows² × Cols) time.