Subarray with Maximum Total: Kadane's algorithm explained

An Adobe phone screen opens with: "Given an integer array, find the contiguous subarray with the largest sum." You've seen this one before. This is Subarray with Maximum Total, also known as Maximum Subarray on other platforms and as Kadane's Algorithm in algorithm textbooks. It's one of the most frequently asked array problems at Adobe, Google, Amazon, and Microsoft, and it sits on the Blind 75 list. The problem tests whether you can maintain running state across a single pass instead of checking every possible subarray.

TL;DR

Walk through the array left to right, maintaining two values: currentSum (the best subarray ending at the current position) and maxSum (the best seen anywhere). At each element, decide: is it better to extend the previous subarray or start fresh from this element? That decision is currentSum = max(nums[i], currentSum + nums[i]). Then update maxSum = max(maxSum, currentSum). One pass, O(n) time, O(1) space.

The Problem

Given an integer array nums, find the contiguous subarray (at least one element) with the largest sum, and return that sum.

maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) => 6
maxSubArray([1]) => 1
maxSubArray([5,4,-1,7,8]) => 23

The subarray must be contiguous. You cannot skip elements. For the first example, the subarray [4,-1,2,1] has the largest sum of 6.

Why Brute Force Fails

The naive approach checks every possible subarray: pick a start index, pick an end index, sum the elements between them. With two nested loops, that's O(n^2) subarrays and O(n) time to sum each (or O(n^2) with a running sum optimization). Either way, n can reach 100,000, so O(n^2) is too slow.

The insight is that you don't need to track every subarray. You only need to track the best subarray ending at the current position. If that running sum goes negative, any future subarray is better off starting fresh than carrying the negative baggage.

Kadane's Algorithm

The algorithm maintains two variables:

• currentSum: the maximum subarray sum ending at the current index
• maxSum: the maximum subarray sum found so far

At each element, you make a single decision: should I extend the current subarray by adding this element, or should I start a new subarray from this element?

The decision is: currentSum = max(nums[i], currentSum + nums[i]).

If currentSum + nums[i] is less than nums[i] alone, the running sum has become a liability. Drop it and start fresh.

Full Walkthrough: [-2,1,-3,4,-1,2,1,-5,4]

Follow currentSum (abbreviated cur) and maxSum (abbreviated max) through the array. The answer is 6, reached at index 6 when the subarray [4,-1,2,1] completes. Notice how maxSum never decreases, only updates when currentSum finds something better.

The Reset Decision

The most important moment in the walkthrough is index 3, where nums[i] = 4. At that point, currentSum is -2 from the previous elements. The algorithm computes max(4, -2 + 4) = max(4, 2) = 4 and starts fresh.

Starting a new subarray at 4 is better than dragging the negative prefix along. This is the core insight of Kadane's algorithm: negative running sums are never worth keeping.

Edge Cases

All Negative Numbers

When every element is negative, the answer is the single least-negative element. Kadane's handles this naturally because max(nums[i], currentSum + nums[i]) always picks the lone element when the running sum only makes things worse.

For [-1,-2,-3,-4], the answer is -1. Each step resets to the current element because extending would produce a more negative sum.

All Positive Numbers

When every element is positive (or nearly so), the entire array is the answer. The running sum never resets because extending always helps.

For [5,4,-1,7,8], the small -1 at index 2 doesn't trigger a reset because 8 + (-1) = 7 is still better than starting fresh at -1. The answer is 23.

Single Element

A single-element array returns that element. No iteration needed since maxSum is initialized to nums[0].

Implementation

Prefer a different language? Jump to solutions in other languages.

public class Solution {

  public int maxSubArray(int[] nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
      currentSum = Math.max(nums[i], currentSum + nums[i]);
      maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
  }
}

A few notes about the implementation:

• Both maxSum and currentSum initialize to nums[0], not to 0 or Integer.MIN_VALUE. This handles the all-negative case correctly without special-casing it.
• The loop starts at index 1 since index 0 is already accounted for in the initialization.
• The two Math.max calls are the entire algorithm. The first decides "extend or reset." The second decides "is this the new best?"

Complexity Analysis

Time: O(n)

One pass through the array. Each element is visited exactly once with O(1) work per element. No sorting, no nested loops.

Space: O(1)

Two integer variables (currentSum and maxSum). No additional arrays or data structures. The space is constant regardless of input size.

The DP Perspective

Kadane's algorithm is actually dynamic programming in disguise. Define dp[i] as the maximum subarray sum ending at index i. The recurrence is:

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

The answer is max(dp[0], dp[1], ..., dp[n-1]).

A full DP array would use O(n) space, but since dp[i] depends only on dp[i-1], you can replace the array with a single variable. That variable is currentSum. This space optimization is why Kadane's runs in O(1) space while still being a DP solution.

Common Mistakes

• Initializing maxSum to 0. This fails when all elements are negative. The algorithm would return 0 (an empty subarray), which isn't valid since the problem requires at least one element. Always initialize to nums[0].

• Clamping currentSum to 0 instead of using max. Some versions set currentSum = 0 when it goes negative. This works when the array has at least one positive number, but fails for all-negative arrays. The max(nums[i], currentSum + nums[i]) formulation handles every case.

• Off-by-one on the loop start. Since maxSum and currentSum are initialized with nums[0], the loop must start at index 1. Starting at 0 double-counts the first element (the self-comparison is harmless but wasteful and confusing).

• Confusing subarray with subsequence. A subarray is contiguous. A subsequence can skip elements. If you're summing all positive elements, you're solving the wrong problem.

Interview Tips

• State the approach upfront. "I'll maintain a running sum of the best subarray ending at each position and a global max. At each step, I decide whether to extend or restart. This is Kadane's algorithm."
• Trace through the example. Walk through [-2,1,-3,4,-1,2,1,-5,4] with the interviewer, showing how currentSum resets at index 3 and how maxSum freezes at 6 after index 6.
• Explain the DP connection. Mention that this is a space-optimized DP where dp[i] = max(nums[i], dp[i-1] + nums[i]), and you're collapsing the array into a single variable.
• Handle the all-negative case explicitly. Point out that initializing to nums[0] (not 0) is what makes the algorithm correct for all-negative inputs.
• Know the follow-ups. Maximum Product Subarray changes addition to multiplication and requires tracking both min and max (sign flips). Maximum Circular Subarray uses a min-subarray trick. Being ready for these shows depth.

Related Problems

Maximum Subarray is the foundation for a family of running-state array problems:

• Maximum Product Subarray - Same structure but with multiplication. Track both min and max products because a negative times a negative can become the new max.
• Maximum Circular Subarray - The subarray can wrap around the end of the array. Use max(kadane_max, total_sum - kadane_min) to handle the wrap.
• Minimum Size Subarray Sum - Find the shortest subarray with a sum >= target. Uses a sliding window instead of Kadane's, but the "maintain running state" idea is the same.
• Maximum Sum of Two Non-Overlapping Subarrays - Combines prefix sums with Kadane's-style tracking.

The "extend or restart" decision pattern from Kadane's appears in all of these. Once you internalize it for the basic version, the variations become manageable extensions.

Ready to practice array problems? Firecode sequences related problems using spaced repetition so you build intuition for running-state patterns over time. Over 50,000 engineers have used it to prepare for interviews at top companies like Adobe, Google, and Amazon.

Solutions in Other Languages

Python

from typing import List

class Solution:
    def max_sub_array(self, nums: List[int]) -> int:
        max_sum = nums[0]
        current_sum = nums[0]

        for num in nums[1:]:
            current_sum = max(num, current_sum + num)
            max_sum = max(max_sum, current_sum)

        return max_sum

JavaScript

class Solution {
  maxSubArray(nums) {
    let maxSum = nums[0];
    let currentSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
      currentSum = Math.max(nums[i], currentSum + nums[i]);
      maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
  }
}

TypeScript

class Solution {
  maxSubArray(nums: number[]): number {
    let maxSum = nums[0];
    let currentSum = nums[0];

    for (let i = 1; i < nums.length; i++) {
      currentSum = Math.max(nums[i], currentSum + nums[i]);
      maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
  }
}

C++

#include <vector>
#include <algorithm>

class Solution {
public:
  int maxSubArray(std::vector<int> &nums) {
    int maxCurrent = nums[0];
    int maxGlobal = nums[0];

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

    return maxGlobal;
  }
};

Go

func (s *Solution) MaxSubArray(nums []int) int {
    maxSum := nums[0]
    currentSum := nums[0]

    for i := 1; i < len(nums); i++ {
        if nums[i] > currentSum + nums[i] {
            currentSum = nums[i]
        } else {
            currentSum = currentSum + nums[i]
        }
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }

    return maxSum
}

Go lacks a built-in max for integers (prior to Go 1.21), so the implementation uses explicit if comparisons instead.

Scala

class Solution {
  def maxSubArray(nums: Array[Int]): Int = {
    var maxSoFar = nums(0)
    var maxEndingHere = nums(0)

    for (i <- 1 until nums.length) {
      maxEndingHere = math.max(nums(i), maxEndingHere + nums(i))
      maxSoFar = math.max(maxSoFar, maxEndingHere)
    }

    maxSoFar
  }
}

Kotlin

class Solution {
    fun maxSubArray(nums: IntArray): Int {
        var maxSum = nums[0]
        var currentSum = nums[0]

        for (i in 1 until nums.size) {
            currentSum = maxOf(nums[i], currentSum + nums[i])
            maxSum = maxOf(maxSum, currentSum)
        }

        return maxSum
    }
}

Swift

import Foundation

class Solution {
    func maxSubArray(_ nums: [Int]) -> Int {
        var maxSum = nums[0]
        var currentSum = nums[0]

        for i in 1..<nums.count {
            currentSum = max(nums[i], currentSum + nums[i])
            maxSum = max(maxSum, currentSum)
        }

        return maxSum
    }
}

Rust

impl Solution {
    pub fn max_sub_array(&self, nums: Vec<i32>) -> i32 {
        let mut max_sum = nums[0];
        let mut current_sum = nums[0];

        for i in 1..nums.len() {
            current_sum = nums[i].max(current_sum + nums[i]);
            max_sum = max_sum.max(current_sum);
        }

        max_sum
    }
}

C#

public class Solution {
    public int maxSubArray(int[] nums) {
        int maxSum = nums[0];
        int currentSum = nums[0];

        for (int i = 1; i < nums.Length; i++) {
            currentSum = Math.Max(nums[i], currentSum + nums[i]);
            maxSum = Math.Max(maxSum, currentSum);
        }

        return maxSum;
    }
}

Dart

import 'dart:math';

class Solution {
  int maxSubArray(List<int> nums) {
    int maxSum = nums[0];
    int currentSum = nums[0];

    for (int i = 1; i < nums.length; i++) {
      currentSum = max(nums[i], currentSum + nums[i]);
      maxSum = max(maxSum, currentSum);
    }

    return maxSum;
  }
}

PHP

class Solution {
    public function maxSubArray(array $nums): int {
        $maxSum = $nums[0];
        $currentSum = $nums[0];

        for ($i = 1; $i < count($nums); $i++) {
            $currentSum = max($nums[$i], $currentSum + $nums[$i]);
            $maxSum = max($maxSum, $currentSum);
        }

        return $maxSum;
    }
}

Ruby

class Solution
  def max_sub_array(nums)
    max_sum = nums[0]
    current_sum = nums[0]

    (1...nums.length).each do |i|
      current_sum = [nums[i], current_sum + nums[i]].max
      max_sum = [max_sum, current_sum].max
    end

    max_sum
  end
end