Speed Up Maximum Subarray

The slow code

Every case must finish within 300 ms (budgets are per language in the editor).

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;
}

function maxSubArray(nums: number[]): number {
  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;
}

def max_sub_array(nums: list[int]) -> int:
    best = nums[0]
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            if total > best:
                best = total
    return best

<?php

function maxSubArray(array $nums): int
{
    $best = PHP_INT_MIN;
    $n = count($nums);
    for ($i = 0; $i < $n; $i++) {
        $sum = 0;
        for ($j = $i; $j < $n; $j++) {
            $sum += $nums[$j];
            if ($sum > $best) {
                $best = $sum;
            }
        }
    }
    return $best;
}

class Solution {
    public int maxSubArray(int[] nums) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = 0;
            for (int j = i; j < nums.length; j++) {
                sum += nums[j];
                if (sum > best) best = sum;
            }
        }
        return best;
    }
}

Solution and explanation

Show the solution

Time O(n) · Space O(1)

Why it is slow: every start position is extended to the end of the array: n(n+1)/2 additions, 1.8 billion for 60,000 numbers.

The fix (Kadane's algorithm): keep cur, the best sum of a subarray ending at the current index: cur = max(x, cur + x). A negative running sum can never help what comes next, so it is dropped. The answer is the maximum cur seen. One pass, O(1) memory.

Initialise with the first element (not 0) so all-negative arrays return their largest element.

Optimized solution

function maxSubArray(nums) {
  let cur = nums[0]; // best sum of a subarray ending here
  let 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;
}

function maxSubArray(nums: number[]): number {
  let cur = nums[0]; // best sum of a subarray ending here
  let 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;
}

def max_sub_array(nums: list[int]) -> int:
    cur = best = nums[0]  # cur: best sum of a subarray ending here
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best

<?php

function maxSubArray(array $nums): int
{
    $cur = $best = $nums[0]; // $cur: best sum of a subarray ending here
    $n = count($nums);
    for ($i = 1; $i < $n; $i++) {
        $cur = max($nums[$i], $cur + $nums[$i]);
        $best = max($best, $cur);
    }
    return $best;
}

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], best = nums[0]; // cur: best sum of a subarray ending here
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

Common mistakes

Initialising best = 0: wrong for all-negative input.
Resetting cur to 0 after updating best in the wrong order.

Follow-up questions

Return the start and end indices too.
Circular array version (maximum circular subarray).

Example 1

Example 2

The slow code

Hints

Make it faster

Solution and explanation

Optimized solution

Common mistakes

Follow-up questions

Example 1

Example 2

The slow code

Hints

Make it faster

Solution and explanation

Optimized solution

Common mistakes

Follow-up questions

More Code Clinic: Make It Fast problems