Skip to main content

7. Maximum Subarray

easyAsked at Udemy

Find the contiguous subarray with the largest sum — Udemy uses Kadane to test whether you can recognize a DP pattern in a casual array problem.

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

Problem

Given an integer array nums, return the largest sum of any contiguous subarray of length at least one.

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

Example 2

Input
nums=[1]
Output
1

Approaches

1. Brute force

Try every subarray.

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

Tradeoff:

2. Kadane

Track the best subarray ending at i: either extend the previous one or start fresh. The global best is the max over all i.

Time
O(n)
Space
O(1)
function maxSubArray(nums) {
  let best = nums[0], 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:

Udemy-specific tips

Udemy interviewers often extend Kadane to finding the best window of daily course-revenue deltas — be ready to discuss negative-only inputs and reset semantics.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →