Skip to main content

53. Maximum Subarray

easyAsked at Juniper Networks

Find the contiguous subarray with the largest sum using Kadane's algorithm. Juniper engineers recognize this O(n) pattern when analyzing network throughput time series — finding the burst window with the highest cumulative data rate is the same greedy subarray problem.

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

Source citations

Public interview reports confirming this problem appears in Juniper Networks loops.

  • Glassdoor (2026-Q1)— Reported in Juniper SWE onsite reports as a frequent array/greedy question.
  • Blind (2025-11)— Listed in Juniper candidate prep threads as a must-know classic.

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

Example 3

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

Explanation: The entire array is the optimal subarray.

Approaches

1. Brute force — O(n²)

Try every subarray start and end pair, compute the sum, track the maximum.

Time
O(n²)
Space
O(1)
function maxSubArray(nums) {
  let max = -Infinity;
  for (let i = 0; i < nums.length; i++) {
    let sum = 0;
    for (let j = i; j < nums.length; j++) {
      sum += nums[j];
      max = Math.max(max, sum);
    }
  }
  return max;
}

Tradeoff: O(n²). Use this to illustrate the suboptimal approach, then pivot to Kadane's.

2. Kadane's algorithm — O(n)

At each index, decide whether to extend the current subarray or start fresh. The running sum is: max(nums[i], currentSum + nums[i]).

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. Kadane's algorithm. The greedy decision at each step (extend vs restart) is optimal because a negative running sum only hurts future sums.

Juniper Networks-specific tips

Name Kadane's algorithm explicitly — Juniper interviewers will probe whether you know classical algorithms by name. Explain the greedy intuition: if the running sum goes negative, it is always better to start fresh from the current element. Draw the analogy to network monitoring: finding the peak throughput window in a stream of delta samples uses the same pattern.

Common mistakes

  • Initializing maxSum to 0 — fails on all-negative arrays; initialize to nums[0].
  • Not seeding currentSum with nums[0] — the loop should start at index 1.
  • Confusing maximum subarray sum with maximum subarray length.
  • Using a divide-and-conquer approach without knowing its O(n log n) cost — Kadane is strictly better.

Follow-up questions

An interviewer at Juniper Networks may pivot to one of these next:

  • Return the actual subarray indices, not just the sum.
  • Maximum Product Subarray (LC 152) — Kadane's analog for products; need to track both max and min.
  • How would you solve this 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

What if all numbers are negative?

Kadane's handles it because we initialize both currentSum and maxSum to nums[0] and the loop starts at index 1. The single least-negative element is returned.

Does the subarray have to be non-empty?

Yes per the problem statement. Initializing to nums[0] enforces this.

How would you track the actual subarray bounds?

Keep start, end, and tempStart indices. Reset tempStart to i when you restart the subarray (currentSum becomes nums[i]). Update start and end when maxSum is updated.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →