Skip to main content

53. Maximum Subarray

easyAsked at Akamai

Find the contiguous subarray with the largest sum. Akamai ties this directly to network throughput analysis — Kadane's algorithm is the canonical one-pass scan for detecting the peak burst window in a stream of per-second byte-delta measurements.

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

Source citations

Public interview reports confirming this problem appears in Akamai loops.

  • Glassdoor (2026-Q1)— Akamai SWE interview reports list Maximum Subarray as a classic array question asked in onsite coding rounds.
  • Blind (2025-10)— Akamai threads confirm Kadane's algorithm is a common probe for DP understanding at all experience levels.

Problem

Given an integer array nums, find the subarray with the largest sum and return its sum. A subarray is a contiguous non-empty portion of the array.

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; that is the subarray.

Example 3

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

Explanation: The entire array is the maximum subarray.

Approaches

1. Kadane's algorithm

Maintain a running sum. At each element, decide whether to extend the current subarray or start fresh. The running sum resets to 0 (start fresh) whenever it would go negative.

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. The cleanest solution. Initializing both sums to nums[0] instead of -Infinity or 0 correctly handles all-negative arrays.

2. Divide and conquer

Split the array at the midpoint. The maximum subarray is either in the left half, the right half, or crossing the midpoint. Recursively solve each and combine.

Time
O(n log n)
Space
O(log n) 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);
    // max crossing subarray
    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) time — worse than Kadane's. Show this if the interviewer asks for a divide-and-conquer solution. Akamai may ask about it to test algorithm design depth, but Kadane's is the right answer for production.

Akamai-specific tips

Name the algorithm: 'This is Kadane's algorithm, first published in 1984.' Akamai interviewers appreciate historical and theoretical context. Then add the scale angle: 'At 10^9 measurements per day, the O(1) space means we can run this in a streaming pipeline with no buffering — which is exactly how edge analytics systems work.'

Common mistakes

  • Initializing maxSum to 0 instead of nums[0] — fails for all-negative arrays; the problem requires at least one element.
  • Using currentSum = Math.max(0, currentSum + nums[i]) — same bug: 0 implies an empty subarray is valid.
  • Forgetting to update maxSum inside the loop — only comparing at the end misses intermediate peaks.

Follow-up questions

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

  • Return the actual subarray indices, not just the sum.
  • Maximum Product Subarray (LC 152) — same scan but tracking both max and min products.
  • How would you handle this if the array is circular (Maximum Sum Circular Subarray, 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 does Kadane's algorithm work?

If the running sum becomes negative, any future extension of that subarray would be smaller than just starting fresh at the next element. So we reset. This greedy insight is optimal.

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 — the loop never resets to 0.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →