Skip to main content

7. Maximum Subarray

easyAsked at Reddit

Find the contiguous subarray with the largest sum. Reddit uses this to filter for candidates who recognize Kadane's algorithm — the same running-sum idea that powers their hot-score windowed-vote calculation.

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

Source citations

Public interview reports confirming this problem appears in Reddit loops.

  • Glassdoor (2026-Q1)— Reddit data-platform team phone screen.
  • LeetCode Discuss (2025-11)— Common signal-detection problem reported in Reddit data engineering rounds.

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has 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 sum 6.

Example 2

Input
nums = [1]
Output
1

Example 3

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

Approaches

1. Brute-force all subarrays

Two nested loops, recompute each subarray sum.

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

Tradeoff: Quadratic. Mention only as the anti-pattern.

2. Kadane's algorithm (optimal)

Track best sum ending here and overall best. If running sum drops below 0, reset.

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

Tradeoff: Linear, O(1) space, single pass. Reddit's vote-window aggregator uses an analogous reset rule.

Reddit-specific tips

Reddit interviewers want you to state the recurrence: 'best ending at i is either nums[i] alone or extends best-ending-at-(i-1).' Bonus signal: mention how this generalizes to detecting bursty vote periods on a post (sliding-window variant).

Common mistakes

  • Initializing best to 0 — fails for all-negative arrays.
  • Returning current instead of best (missing intermediate maxima).
  • Resetting current to 0 instead of nums[i] (skips negative-only segments).

Follow-up questions

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

  • Maximum subarray product (LC 152) — needs min and max because of negatives.
  • Return the actual subarray, not just the sum.
  • Divide and conquer version — O(n log n) but elegant.

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 max(nums[i], current+nums[i]) instead of max(0, current)+nums[i]?

They're equivalent when nums[i] can be negative; the form max(nums[i], current+nums[i]) makes the 'restart vs. extend' decision more obvious.

Can this find the subarray itself?

Track start/end indices: when you restart, start = i; when best updates, save (start, i) as the current best range.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →