Skip to main content

17. Maximum Subarray

mediumAsked at Klarna

Find the contiguous subarray with the largest sum.

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

Problem

Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum, and return that 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

Example 2

Input
nums = [1]
Output
1

Approaches

1. Brute force all windows

Enumerate every (i, j) window and recompute its 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];
      if (sum > best) best = sum;
    }
  }
  return best;
}

Tradeoff:

2. Kadane's algorithm

Track the best subarray ending at each index. At each step either extend the prior subarray or start a new one at the current element, whichever is larger.

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]);
    if (cur > best) best = cur;
  }
  return best;
}

Tradeoff:

Klarna-specific tips

Klarna's BNPL credit-scoring jobs use Kadane on time-series spend signals, so they expect you to derive the recurrence cleanly without leaning on prebuilt DP tables.

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 Klarna interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →