Skip to main content

48. Maximum Subarray

mediumAsked at Salesforce

Find the contiguous subarray with the largest sum. Salesforce uses this to test Kadane's algorithm — the canonical O(n) DP and a forecasting-dashboard staple.

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

Source citations

Public interview reports confirming this problem appears in Salesforce loops.

  • Glassdoor (2026-Q1)— Salesforce uses Kadane in their pipeline forecasting and trend detection.
  • Blind (2025-11)— Recurring on Salesforce backend phone screens.

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: [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

Try every (start, end); compute 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: TLE on 10^5 elements. Salesforce wants O(n).

2. Kadane's algorithm

Track the best subarray ending at i. Recurrence: cur = max(nums[i], cur + nums[i]). Global max = max over all i.

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. The recurrence captures the choice: start fresh at i, or extend the prior subarray.

Salesforce-specific tips

Salesforce explicitly grades on whether you know Kadane by name. Bonus signal: articulate the DP recurrence — cur[i] = max(nums[i], cur[i-1] + nums[i]) — and explain WHY you don't need to track the full DP array (only the previous value).

Common mistakes

  • Initializing best to 0 — fails on all-negative arrays (e.g., [-1] should return -1, not 0).
  • Confusing cur (sum ending at i) with best (global max).
  • Forgetting that the subarray must contain at least one element — the problem says non-empty.

Follow-up questions

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

  • Maximum Product Subarray (LC 152) — harder, two state variables.
  • Maximum Subarray of Length K — sliding window variant.
  • 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 is the DP O(1) space?

Because cur[i] depends only on cur[i-1]. We only keep the previous value, not the whole DP array.

When does cur reset to nums[i]?

When cur + nums[i] < nums[i], which means cur < 0. The prior subarray was a net drag, so we start fresh at i.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →