Skip to main content

53. Maximum Subarray

easyAsked at AMD

Find the contiguous subarray with the largest sum. AMD asks this to test Kadane's algorithm — a greedy single-pass technique relevant to performance profiling, where you scan a sequence of GPU frame times to find the worst sustained latency window.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2026-Q1)— AMD SWE candidates report Maximum Subarray as a typical greedy/DP easy in phone screen and onsite rounds.
  • Blind (2025-11)— AMD interview threads cite Kadane's as a must-know algorithm for SWE roles with any performance tooling component.

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: Subarray [4,-1,2,1] has the largest sum = 6.

Example 2

Input
nums = [1]
Output
1

Explanation: Single element.

Example 3

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

Explanation: The whole array is the best subarray.

Approaches

1. Kadane's Algorithm

At each position, decide: extend the current subarray or start fresh from this element. Track the global maximum.

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++) {
    currentSum = Math.max(nums[i], currentSum + nums[i]);
    maxSum = Math.max(maxSum, currentSum);
  }
  return maxSum;
}

Tradeoff: O(n) time, O(1) space. The key insight: if currentSum drops below 0, carrying it forward only hurts the next element, so reset to nums[i].

2. Divide and Conquer

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

Time
O(n log n)
Space
O(log n) call stack
function maxSubArray(nums) {
  function helper(l, r) {
    if (l === r) return nums[l];
    const mid = (l + r) >> 1;
    const leftMax = helper(l, mid);
    const rightMax = helper(mid + 1, r);
    // cross sum
    let leftCross = -Infinity, sum = 0;
    for (let i = mid; i >= l; i--) { sum += nums[i]; leftCross = Math.max(leftCross, sum); }
    let rightCross = -Infinity; sum = 0;
    for (let i = mid + 1; i <= r; 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 D&C mastery. AMD may ask for both to test algorithmic breadth.

AMD-specific tips

AMD telemetry and performance tooling teams scan large arrays of counters. Kadane's is directly applicable: finding the worst contiguous sustained stall window in a performance trace. Mention this connection. Also note the bit-shift `>> 1` for mid-point computation — AMD interviewers appreciate bit-operation fluency. If asked 'can you do it in O(n log n)?', explain D&C as a deliberate trade-off that would suit a parallel implementation on many cores.

Common mistakes

  • Initializing maxSum to 0 — this is wrong when all elements are negative; the answer must be at least nums[0].
  • Not restarting at nums[i] when currentSum + nums[i] < nums[i] — dragging a negative prefix defeats the purpose.
  • Confusing 'sum of subarray' with 'product' — this problem is sum only.
  • Off-by-one in the D&C cross-sum scan — the left scan goes from mid downward (inclusive), right from mid+1 upward.

Follow-up questions

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

  • Maximum Product Subarray (LC 152) — products can sign-flip, requiring tracking both max and min.
  • How would you parallelize Kadane's algorithm across multiple GPU threads?
  • Return the actual subarray indices, not just the 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 does Kadane's work?

At each position, the optimal subarray ending here is either just nums[i] alone (start fresh) or nums[i] plus the best subarray ending at i-1. If the running sum is negative, it hurts any future element, so discarding it is always correct.

What if all numbers are negative?

The algorithm still works — it returns the least-negative single element because currentSum resets to nums[i] whenever that single element is larger than the running sum.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →