Skip to main content

53. Maximum Subarray

easyAsked at HubSpot

HubSpot asks Maximum Subarray to test Kadane's algorithm — one of the most elegant greedy/DP hybrids in the canon — and to see whether you can clearly articulate why dropping a negative prefix always improves the running sum.

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

Source citations

Public interview reports confirming this problem appears in HubSpot loops.

  • Blind (2025-11)— HubSpot SWE candidates cite Maximum Subarray as an occasional screen-round problem with a follow-up on divide-and-conquer.
  • Glassdoor (2026-Q1)— Listed in HubSpot technical interview reports as a test of greedy intuition and DP fundamentals.

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

Explanation: Only one element — the best subarray is the element itself.

Approaches

1. Kadane's algorithm

Track the maximum sum ending at each position. If the running sum becomes negative, reset it to 0 (or to the current element). Update the global maximum at each step.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let maxSum = nums[0];
  let currentSum = nums[0];
  for (let i = 1; i < nums.length; i++) {
    // Either extend the existing subarray or start fresh here
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Tradeoff: O(n) time, O(1) space. The classic answer. Key insight: if currentSum + nums[i] < nums[i], the entire previous subarray is a liability — drop it. Initializing both maxSum and currentSum to nums[0] correctly handles all-negative arrays.

2. Divide and conquer

Split the array at the midpoint. The maximum subarray is either entirely in the left half, entirely in the right half, or crosses the midpoint. Combine results recursively.

Time
O(n log n)
Space
O(log n) call stack
function maxSubArray(nums) {
  function helper(left, right) {
    if (left === right) return nums[left];
    const mid = Math.floor((left + right) / 2);
    const leftMax = helper(left, mid);
    const rightMax = helper(mid + 1, right);
    // Find max crossing subarray
    let leftCross = -Infinity, sum = 0;
    for (let i = mid; i >= left; i--) { sum += nums[i]; leftCross = Math.max(leftCross, sum); }
    let rightCross = -Infinity; sum = 0;
    for (let i = mid + 1; i <= right; i++) { sum += nums[i]; rightCross = Math.max(rightCross, sum); }
    return Math.max(leftMax, rightMax, leftCross + rightCross);
  }
  return helper(0, nums.length - 1);
}

Tradeoff: O(n log n) — worse than Kadane's but demonstrates divide-and-conquer fluency. HubSpot may ask for this as a follow-up to test your recursion depth. Not the default answer.

HubSpot-specific tips

Name the algorithm before writing it: 'This is Kadane's algorithm — a classic O(n) DP/greedy approach.' Explain the core decision: extending vs. restarting the subarray. HubSpot interviewers often ask 'what if all numbers are negative?' — your initialization to nums[0] (not 0) handles that correctly. They may also ask you to return the subarray itself rather than just the sum — be ready to track start and end indices.

Common mistakes

  • Initializing maxSum to 0 — this incorrectly returns 0 for all-negative arrays; initialize to nums[0].
  • Resetting currentSum to 0 instead of nums[i] — same issue for all-negative inputs.
  • Not updating maxSum on every iteration — updating only at the end misses the actual maximum.
  • Confusing the 'restart' condition — restart when currentSum + nums[i] < nums[i], which simplifies to currentSum < 0.

Follow-up questions

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

  • Return the actual subarray (indices), not just the sum — track startIndex and update when restarting.
  • Maximum Product Subarray (LC 152) — multiplying negatives can flip the sign, so track both max and min.
  • What if the array wraps around (circular)? (LC 918) — total sum minus the minimum subarray sum.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why is this considered DP?

The optimal subarray ending at index i depends on the optimal subarray ending at i-1: f(i) = max(nums[i], f(i-1) + nums[i]). That's a DP recurrence with O(1) state.

What if all numbers are negative?

Initializing maxSum = nums[0] ensures the least-negative element is returned. Initializing to 0 would incorrectly return 0, which is not achievable by any subarray.

How does this differ from Maximum Sum of k Consecutive Elements?

That problem uses a fixed-size sliding window. Kadane's solves for any variable-length subarray — you restart when extending would decrease the sum.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →