Skip to content
Coding Patterns - Guide to 30 Core Algorithm Patterns
Kadane's Algorithm: Complete Guide with Examples
Kadane's Algorithm: Code Templates in 6 Languages

Kadane's Algorithm: Code Templates in 6 Languages

If you have not read the concept guide yet, start there for the extend-or-restart intuition and the complexity analysis. This page gives you the code you can memorize and adapt during an interview. Every template here runs in

O(N)
time with
O(1)
extra space unless otherwise noted.

Main Template: Maximum Subarray Sum

This is the standard Kadane’s algorithm in its purest form. Two accumulators track the best subarray ending at the current position and the best subarray seen anywhere so far. At each element the algorithm decides whether to extend the current subarray or restart at the current element.

Use this for Maximum Subarray .

function maxSubArray(nums) {
    // Seed both accumulators with the first element so
    // an all-negative array returns the least negative value.
    let maxEndingHere = nums[0];
    let maxSoFar = nums[0];

    for (let i = 1; i < nums.length; i++) {
        // A negative running total drags down every future
        // element, so restart when the element alone is larger.
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }
    return maxSoFar;
}
Templates only help if you can recall them without staring at the screen. Turn these snippets into flashcards for daily mobile review.

Code Breakdown

Key Variables

  • maxEndingHere: the best subarray sum that ends exactly at the current position. This is the rolling state, the only value that carries forward.
  • maxSoFar: the best subarray sum seen anywhere so far. This is the answer at the end of the loop.
  • The loop index: starts at 1 because index 0 already seeded both accumulators. Re-running the first element would double count it.

Visual Mechanism 

    stateDiagram-v2
    [*] --> Init: maxEndingHere = maxSoFar = nums[0]
    Init --> Decide: i = 1
    Decide --> Extend: nums[i] > maxEndingHere + nums[i]
    Decide --> Restart: nums[i] >= maxEndingHere + nums[i]
    Extend --> Update: maxEndingHere += nums[i]
    Restart --> Update: maxEndingHere = nums[i]
    Update --> Check: compare with maxSoFar
    Check --> Decide: i++
    Check --> Done: i == n
    Done --> [*]

Critical Sections

The initialization seeds both accumulators with nums[0]. This single line is the whole defense against all-negative input. With [-3, -1, -2], the correct answer is -1, and seeding from 0 would return 0 instead.

The extend-or-restart decision is the heart of the pattern. max(nums[i], maxEndingHere + nums[i]) compares two candidates. Extending keeps the previous segment and adds the current element. Restarting discards the previous segment entirely and starts at the current element. The comparison decides which candidate is larger, and the running total becomes that candidate.

The global update runs after the decision, never before. maxSoFar must be compared against the freshly computed running total, because the best subarray can end anywhere, not just at the final index.

Variations

1. Kadane with Indices

Same algorithm, plus bookkeeping to return the start and end of the best subarray instead of just the sum. A temporary start index moves on every restart, but the committed start only changes when a new global maximum appears.

def max_sub_array_with_indices(nums):
    max_so_far = nums[0]
    max_ending_here = nums[0]
    start = end = 0
    temp_start = 0

    for i in range(1, len(nums)):
        if max_ending_here + nums[i] < nums[i]:
            # Restarting. Remember the candidate start now,
            # but do not commit it until this segment actually
            # produces a new global best.
            max_ending_here = nums[i]
            temp_start = i
        else:
            max_ending_here += nums[i]

        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i

    return max_so_far, start, end

The two start variables exist because a restart can be temporary. The segment starting at temp_start might never beat the current global best, and in that case the committed start must not move.

2. Maximum Product Subarray

For products, a negative running total can become an asset. Multiply a negative running product by another negative element and it flips into a large positive. That breaks plain Kadane, so this variation tracks both the maximum and the minimum product ending at each position.

def max_product(nums):
    max_ending_here = nums[0]
    min_ending_here = nums[0]
    max_so_far = nums[0]

    for i in range(1, len(nums)):
        temp_max = max_ending_here

        # The new max can come from the old max, the old min
        # (a negative times a negative), or a fresh start.
        max_ending_here = max(nums[i], max_ending_here * nums[i], min_ending_here * nums[i])
        min_ending_here = min(nums[i], temp_max * nums[i], min_ending_here * nums[i])

        max_so_far = max(max_so_far, max_ending_here)

    return max_so_far

The extra variable temp_max is not a stylistic choice. The new minimum is computed from the old maximum, so the old maximum must be saved before it is overwritten.

3. Circular Maximum Subarray

A subarray in a circular array either sits inside the array, in which case standard Kadane handles it, or it wraps around the ends. A wrapping subarray is the complement of a contiguous middle segment, so its sum is the total sum minus the minimum subarray sum. Run Kadane twice, once for the maximum and once for the minimum.

function maxSubarraySumCircular(nums) {
    let maxEndingHere = nums[0], maxSoFar = nums[0];
    for (let i = 1; i < nums.length; i++) {
        maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
        maxSoFar = Math.max(maxSoFar, maxEndingHere);
    }

    const total = nums.reduce((a, b) => a + b, 0);
    let minEndingHere = nums[0], minSoFar = nums[0];
    for (let i = 1; i < nums.length; i++) {
        minEndingHere = Math.min(nums[i], minEndingHere + nums[i]);
        minSoFar = Math.min(minSoFar, minEndingHere);
    }

    // All-negative guard. When the minimum subarray is the whole
    // array, total - minSoFar would be 0, an empty subarray.
    if (minSoFar === total) return maxSoFar;

    return Math.max(maxSoFar, total - minSoFar);
}

The all-negative guard is easy to forget and it is what makes this variation a separate review card. Without it, [-3, -2, -3] returns 0 instead of -2.

Each variation above is a separate review card in the app. Drill them individually so you do not mix up the conditions under pressure.

Now head to the practice problems to apply these templates to real interview questions.

Now that you have the templates, the next step is application. Head to the practice problems or start reviewing these templates with spaced repetition .