Skip to main content

7. Maximum Subarray

mediumAsked at Workday

Find the contiguous subarray with the largest sum. Workday uses this to test Kadane's pattern for finding the best fiscal-quarter window of an employee's incremental bonuses.

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

Source citations

Public interview reports confirming this problem appears in Workday loops.

  • Glassdoor (2026-Q1)— Workday SDE2 onsite — DP warmup before harder DP.
  • Blind (2025)— Workday Pleasanton phone screen.

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

Example 3

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

Approaches

1. Brute force all subarrays

For each start, accumulate and track best.

Time
O(n^2)
Space
O(1)
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. Fine for n=100, dies at n=10^5.

2. Kadane's algorithm

At each index, either extend the running subarray or start fresh. Take the max running with the global best.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let best = nums[0];
  let cur = 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 'extend or restart' decision is the entire insight.

Workday-specific tips

Workday loves the all-negative case (e.g., nums = [-1, -2, -3]) — candidates who init best to 0 silently produce 0 instead of -1. Walk through this case verbally. Also, mention Kadane by name; it earns 'has seen this before but is also articulating the why' credit.

Common mistakes

  • Initializing best to 0 — fails on all-negative inputs.
  • Skipping the i = 0 element when initializing cur.
  • Confusing 'subarray' (contiguous) with 'subsequence' (non-contiguous).

Follow-up questions

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

  • Return the actual subarray, not just the sum.
  • Maximum Subarray Sum with circular array (LC 918).
  • What if you can skip at most k elements?

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], cur + nums[i])?

Either you extend the previous window or you restart at nums[i]. If the previous sum is negative, restarting wins. This is Kadane in one line.

Can I solve this with divide-and-conquer?

Yes — O(n log n). Mention it but don't code it; Kadane is what interviewers want.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →