Skip to main content

53. Maximum Subarray

easyAsked at Linear

Find the contiguous subarray with the largest sum. Linear uses this to see if you know Kadane's algorithm by name and can articulate the 'restart if running sum goes negative' intuition before writing a single line of code.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Source citations

Public interview reports confirming this problem appears in Linear loops.

  • Glassdoor (2026-Q1)— Recurring in Linear SWE phone screen reports as a DP/greedy warm-up.
  • Blind (2025-11)— Cited in Linear interview threads as a benchmark problem for DP familiarity.

Problem

Given an integer array nums, find the subarray with the largest sum and return its sum.

Constraints

  • 1 <= nums.length <= 10^5
  • -10^4 <= nums[i] <= 10^4

Examples

Example 1

Input
nums = [-2,1,-3,4,-1,2,1,-5,4]
Output
6

Explanation: The subarray [4,-1,2,1] has the largest sum = 6.

Example 2

Input
nums = [1]
Output
1

Example 3

Input
nums = [5,4,-1,7,8]
Output
23

Approaches

1. Brute force all subarrays

Enumerate every subarray start and end, compute the sum, track the maximum.

Time
O(n^2)
Space
O(1)
function maxSubArray(nums) {
  let max = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      max = Math.max(max, sum);
    }
  }
  return max;
}

Tradeoff: O(n^2). Correct, but use this only as a baseline before pivoting to Kadane's.

2. Kadane's algorithm (optimal)

Scan once. At each position, either extend the current subarray or start fresh at the current element — whichever is larger.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let currentSum = nums[0];
  let maxSum = 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;
}

Tradeoff: O(n) time, O(1) space. Key insight: if currentSum is negative before adding the next element, discard it — a fresh start from nums[i] is always better than dragging a negative prefix.

Linear-specific tips

Name the algorithm immediately: 'This is Kadane's algorithm.' Then explain the invariant before coding: 'At each step, the best subarray ending at position i is either nums[i] alone, or nums[i] extended from the best subarray ending at i-1.' Linear values verbal precision as much as correct code.

Common mistakes

  • Initializing maxSum to 0 — fails on all-negative arrays where the answer is the least-negative element.
  • Not restarting the running sum when it goes negative — carrying a negative prefix always reduces the total.
  • Returning maxSum before the loop finishes — the maximum may appear anywhere in the array.

Follow-up questions

An interviewer at Linear may pivot to one of these next:

  • Maximum Product Subarray (LC 152) — must track both min and max due to negative * negative = positive.
  • What if you need to return the actual subarray, not just the sum? (Track start and end indices.)
  • Maximum Sum Circular Subarray (LC 918) — wrap-around case.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

What if all elements are negative?

The answer is the single largest (least-negative) element. Initializing both currentSum and maxSum to nums[0] handles this correctly.

Is this DP or greedy?

Both framings are valid. The DP framing: dp[i] = max subarray sum ending at i. The greedy framing: always extend if the running sum is positive, restart otherwise. Linear interviewers accept either — just be consistent.

How do I also return the subarray indices?

Track a 'start candidate' and update the actual start/end when you restart or find a new maximum. This adds O(1) bookkeeping without changing the complexity.

Practice these live with InterviewChamp.AI

Drill Maximum Subarray and other Linear interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →