Skip to main content

53. Maximum Subarray

easyAsked at eBay

eBay's analytics teams compute rolling revenue windows — 'what was the best consecutive streak of profitable days this quarter?' Maximum Subarray (Kadane's algorithm) is the canonical solution. It's asked at eBay because it distinguishes candidates who memorize solutions from those who can derive the greedy insight on the spot.

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

Source citations

Public interview reports confirming this problem appears in eBay loops.

  • Glassdoor (2025-11)— Reported in eBay mid-level SWE interviews as a test of greedy / DP intuition.
  • Blind (2025-09)— eBay SWE candidates list Maximum Subarray as a common easy-to-medium problem in the first two rounds.

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: Single element — the only subarray is the element itself.

Example 3

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

Explanation: The entire array [5,4,-1,7,8] sums to 23.

Approaches

1. Kadane's Algorithm

At each position, decide: extend the current subarray or start fresh at this element. The current subarray is worth extending only if its running sum is positive.

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 the current subarray or start a new one here
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Tradeoff: O(n) time, O(1) space — optimal. The key recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]). Name this Kadane's algorithm; eBay interviewers respond well to knowing the algorithm's name and origin.

2. Divide and Conquer

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

Time
O(n log n)
Space
O(log n) call stack
function maxSubArray(nums) {
  function helper(lo, hi) {
    if (lo === hi) return nums[lo];
    const mid = Math.floor((lo + hi) / 2);
    const leftMax = helper(lo, mid);
    const rightMax = helper(mid + 1, hi);
    // Compute max crossing subarray
    let leftCross = -Infinity, sum = 0;
    for (let i = mid; i >= lo; i--) { sum += nums[i]; leftCross = Math.max(leftCross, sum); }
    let rightCross = -Infinity; sum = 0;
    for (let i = mid + 1; i <= hi; 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) — slower than Kadane's but demonstrates divide-and-conquer mastery. Mention this as an alternative if the interviewer asks for a different approach.

eBay-specific tips

eBay interviewers want you to derive the greedy insight, not recite it. Say: 'At each element, I ask — is it better to extend my current subarray or start fresh? If my running sum would make the total smaller than just this element alone, I start over.' Then name Kadane's algorithm. The follow-up 'return the actual subarray indices' (LC 53 variant) is common — track start/end pointers when currentSum resets.

Common mistakes

  • Initializing currentSum and maxSum to 0 instead of nums[0] — this incorrectly returns 0 for all-negative arrays.
  • Resetting currentSum to 0 when negative instead of to nums[i] — misses the 'best single element' case.
  • Not handling the single-element case separately — it works with the algorithm above, but verify mentally.
  • Using O(n) extra space for a DP array when two variables suffice.

Follow-up questions

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

  • Return the actual subarray (start and end indices), not just the sum.
  • Maximum Product Subarray (LC 152) — same greedy idea, but tracking both min and max because negatives flip signs.
  • How would you compute the maximum subarray sum for a circular array (LC 918)?

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 -Infinity?

Initializing to nums[0] handles all-negative arrays correctly — the answer is the largest (least negative) element. Using -Infinity works too but requires an off-by-one loop start.

What is Kadane's algorithm?

A linear-time greedy/DP algorithm by Jay Kadane (1984) for finding the maximum sum contiguous subarray. The recurrence is dp[i] = max(nums[i], dp[i-1] + nums[i]).

When would you choose divide and conquer over Kadane's?

Almost never in practice — Kadane's is both simpler and faster. Divide and conquer is a good exercise in technique but inferior in all measurable ways for this specific problem.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →