53. Maximum Subarray

Q: Why initialize to nums[0] and not 0 or -Infinity?

Initializing to -Infinity is technically correct but initializing to nums[0] is cleaner: the answer must include at least one element, so nums[0] is a valid lower bound and avoids handling the -Infinity edge case.

Q: When does Kadane's reset currentSum?

When currentSum + nums[i] < nums[i], i.e., when currentSum < 0. A negative prefix always hurts the total — better to start a new subarray at nums[i].

Q: Does divide and conquer have practical advantages?

It's more naturally parallelizable — each half can be processed on a separate core. For very large distributed data sets this matters, but Kadane's is still preferred for a single-machine sequential pass.

easyAsked at HP

HP uses signal-processing algorithms in imaging and scanning products where finding the strongest contiguous signal window is a real computational task. Maximum Subarray (Kadane's algorithm) is the archetype: HP interviewers use it to test whether you can identify the single-pass greedy insight in a DP-flavored problem.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in HP loops.

Glassdoor (2026-Q1)— HP backend SWE onsite reports include Maximum Subarray as a common medium-leaning easy question.
Blind (2025-11)— HP interview preparation threads list Kadane's algorithm problems as recurring topics in technical screens.

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

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

Example 2

Input

nums = [1]

Output

Explanation: Single element; the subarray is [1] with sum 1.

Example 3

Input

nums = [5,4,-1,7,8]

Output

Explanation: The entire array has the maximum sum.

Approaches

1. Kadane's algorithm

Track the maximum subarray sum ending at the current index. At each step, decide whether to extend the current subarray or start a new one from the current element.

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++) {
    // Either extend current subarray or start fresh at nums[i]
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Tradeoff: O(n) time, O(1) space. The canonical solution. The key insight: if currentSum drops below zero, it's better to abandon it and start fresh at the next element.

2. Divide and conquer

Split the array in half. The maximum subarray is either entirely in the left half, the right half, or crosses the midpoint. Recursively solve left and right; compute the max cross-sum explicitly.

Time: O(n log n)
Space: O(log n)

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);
    // Max crossing sum
    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) time — worse than Kadane's, but demonstrates divide-and-conquer thinking. HP may ask for this approach explicitly to test recursive problem decomposition.

HP-specific tips

HP interviewers appreciate hearing both approaches. Start with Kadane's as the optimal solution, then mention divide-and-conquer to show breadth. A common HP follow-up is to return the actual subarray (not just the sum) — track start/end indices in your Kadane's implementation. For all-negative arrays, the answer is the single largest element, not zero — Kadane's handles this correctly by initializing from nums[0].

Common mistakes

Initializing currentSum and maxSum to 0 instead of nums[0] — fails when all elements are negative.
Forgetting to update maxSum inside the loop — you miss intermediate maxima.
Confusing the decision: 'take nums[i] alone vs. append to currentSum' — Math.max(nums[i], currentSum + nums[i]) captures this exactly.
Off-by-one errors in the divide-and-conquer cross-sum computation — iterate from mid leftward and from mid+1 rightward separately.

Follow-up questions

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

Return the actual subarray indices, not just the sum.
Find the maximum subarray sum in a circular array (LC 918).
What if the array is a 2D matrix — find the sub-rectangle with the maximum 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 initialize to nums[0] and not 0 or -Infinity?

Initializing to -Infinity is technically correct but initializing to nums[0] is cleaner: the answer must include at least one element, so nums[0] is a valid lower bound and avoids handling the -Infinity edge case.

When does Kadane's reset currentSum?

When currentSum + nums[i] < nums[i], i.e., when currentSum < 0. A negative prefix always hurts the total — better to start a new subarray at nums[i].

Does divide and conquer have practical advantages?

It's more naturally parallelizable — each half can be processed on a separate core. For very large distributed data sets this matters, but Kadane's is still preferred for a single-machine sequential pass.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →