Skip to main content

53. Maximum Subarray

easyAsked at Cohere

Find the contiguous subarray with the largest sum. Cohere asks this because Kadane's algorithm demonstrates the greedy DP reasoning that underlies attention-window selection and relevance-score aggregation in retrieval pipelines.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2026-Q1)— Cohere SWE candidates report Maximum Subarray as a standard medium-easy question in phone screens.
  • Blind (2025-11)— Cohere Blind threads identify Kadane's algorithm as an expected knowledge baseline for engineering interviews.

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

Example 2

Input
nums = [1]
Output
1

Explanation: Single-element array.

Example 3

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

Explanation: The entire array is the maximum subarray.

Approaches

1. Brute force

Try all O(n²) subarrays and track the maximum sum.

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²) — illustrates the problem but too slow for 10^5 elements.

2. Kadane's algorithm

Maintain a running sum. If the running sum drops below 0, reset it to 0 (it is never worth dragging a negative prefix into the next subarray).

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let maxSum = -Infinity;
  let currentSum = 0;
  for (const num of nums) {
    currentSum += num;
    maxSum = Math.max(maxSum, currentSum);
    if (currentSum < 0) currentSum = 0;
  }
  return maxSum;
}

Tradeoff: O(n) time, O(1) space — the canonical answer. The key insight: a negative prefix always hurts, so discard it greedily.

Cohere-specific tips

Cohere interviewers may follow up by asking you to return the actual subarray indices, not just the sum. Track start and end pointers: when currentSum < 0 reset, record the potential new start as i+1, and whenever maxSum updates record the current start and end. This extension tests your ability to adapt an elegant algorithm to a slightly richer specification — common in Cohere's applied ML contexts.

Common mistakes

  • Initialising maxSum to 0 — fails when all elements are negative; use -Infinity or nums[0].
  • Resetting currentSum after updating maxSum — you must update maxSum before resetting.
  • Not handling single-element arrays — Kadane's handles them correctly as long as maxSum starts at -Infinity.
  • Forgetting the return indices variant when the interviewer asks for the subarray itself.

Follow-up questions

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

  • Return the actual subarray, not just the sum.
  • Maximum Product Subarray — similar greedy logic but must track both max and min due to sign flips.
  • How would you find the maximum subarray sum in 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

Why initialise maxSum to -Infinity?

If all elements are negative, the maximum subarray is the least-negative single element. Starting at 0 would incorrectly return 0.

Is there a divide-and-conquer solution?

Yes — O(n log n). Split the array, find max subarrays in left and right halves, and find the max crossing subarray. Not optimal but worth knowing for follow-ups about parallelism.

What is the DP formulation?

dp[i] = max(nums[i], dp[i-1] + nums[i]). Kadane's is the space-optimised version of this recurrence.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →