Skip to main content

7. Maximum Subarray

easyAsked at Databricks

Find the contiguous subarray with the largest sum. Databricks asks this to test Kadane's algorithm and to set up the harder question: 'now do it on a Spark DataFrame partitioned across the cluster.'

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

Source citations

Public interview reports confirming this problem appears in Databricks loops.

  • Blind (2025-12)— Databricks runtime team — Kadane warm-up then distributed prefix-sum variant.
  • LeetCode Discuss (2026-Q1)— Reported as the canonical Databricks Kadane question.

Problem

Given an integer array nums, find the subarray with the largest sum, and return its sum. A subarray is a contiguous non-empty sequence of elements within an 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: [4,-1,2,1] has the largest 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

Enumerate every (i, j) pair, sum from i to j, track max.

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 to motivate the next step.

2. Kadane's algorithm

Track 'best subarray ending here'. At each index, either extend the previous one or start fresh — whichever is bigger.

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

Tradeoff: Single pass, O(1) space. The trick: 'extend or restart' is a local decision — no need to remember boundaries.

Databricks-specific tips

Databricks loves the follow-up: 'now nums is a Spark RDD partitioned across 1000 machines.' The trick is that max-subarray is an associative reduce — each partition returns (totalSum, prefixMax, suffixMax, bestInside) and the merge combines them. If you can derive that monoid on the whiteboard, you've shown you understand the distributed pattern Databricks engineers think in. Articulate this even if not asked.

Common mistakes

  • Initializing best to 0 — fails on all-negative arrays.
  • Returning the subarray instead of the sum — read the prompt.
  • Thinking Kadane needs DP table — it's O(1) space because each step only depends on the previous one.

Follow-up questions

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

  • Return the actual subarray (start, end indices).
  • Distributed: partition the array; design the per-partition state and the associative merge.
  • 2D version: maximum subrectangle (LC 363).

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 is the 'extend or restart' rule correct?

If the running sum is negative, dragging it forward only hurts. Restarting at nums[i] is at least as good as nums[i] + (negative).

How does this map to Spark?

It's an associative monoid: per-partition state is (sum, prefixMax, suffixMax, best), and you can combine adjacent partitions with a constant-time merge — exactly what reduce() needs.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →