Coding interview problems › Arrays & Hashing

#️⃣ Arrays & Hashing Medium

Maximum Subarray (Kadane's Algorithm)

Kadane's algorithm explained with an example: find the maximum-sum subarray in one O(n) pass, all-negative edge case, tested Python and a live visual.

Also searched as: Kadane's algorithm example · largest sum contiguous subarray · maximum subarray sum

📈

Try it live Free

Prefix Sums & Kadane

Watch the O(n²) brute force compared with Kadane's single pass, and see the running sum dropped the moment it goes negative. Try an all-negative array to check the edge case.

Open the playground →

The problem

Given a non-empty list of integers (positive, negative or zero), find the largest possible sum of a contiguous, non-empty subarray.

Inputnums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output6

The subarray [4, -1, 2, 1].

Inputnums = [-3, -1, -2]
Output-1

All negative: the best is the single largest element.

The key insight

Walk left to right and keep the best sum of a subarray that ends here. At each element you have one choice: extend the previous run or start fresh. A run whose sum has gone negative can only hurt whatever comes next, so you drop it. That single decision per element is Kadane's algorithm.

Brute force first: Summing every subarray is O(n²) with a running sum, O(n³) without one.

Step-by-step approach

  1. Set cur = best = nums[0].
  2. For each next element x: cur = max(x, cur + x) (start fresh or extend).
  3. Update best = max(best, cur).
  4. Return best. Initialising with nums[0] instead of 0 keeps the all-negative case correct.

Python solution

PYTHON 3tested
def max_subarray(nums):
    cur = best = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)      # extend the run, or restart at x
        best = max(best, cur)
    return best

Complexity

TimeO(n)
SpaceO(1)

One pass with two running numbers. No extra arrays are needed.

Common mistakes

Frequently asked questions

What is the time and space complexity of Kadane's algorithm?

O(n) time and O(1) space: one pass that tracks the best sum ending at the current element and the best sum seen overall.

How do I return the subarray itself, not just the sum?

Track a start index that resets whenever you restart at x, and record start and end whenever best improves.

Why is Kadane's algorithm considered dynamic programming?

cur is the answer to a subproblem, the best sum of a subarray ending at index i, built from the answer at i - 1. Keeping only the previous value is the space-optimised form of that DP.

What about the maximum circular subarray?

Take the larger of the normal Kadane answer and total sum minus the minimum subarray sum, unless every element is negative, in which case use the normal answer.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Arrays & Hashing Hash Tables lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.