Maximum Subarray

MEDIUM✓ CHIP-TIMEDLC #53 — FULL STATEMENT ↗

The drill: Slice a run of consecutive numbers out of an array so their sum is as large as possible. The run must be nonempty — it can be a single number or the whole array.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

An array of integers arrives, and the goal is picking one contiguous stretch of it — a slice with no gaps or skipped elements — whose values add up to the largest possible sum.

The chosen stretch can never be empty; picking just one number is always allowed, and picking the entire array is too. Negative numbers can and do appear, so the best stretch isn't always the longest one.

Only the maximum sum itself needs reporting — not the stretch's start and end positions or its length.

EX 01

nums = [3, -2, 5, -1]

→ 6

RUN CROSSES THE DIP

EX 02

nums = [-8]

→ -8

SINGLE NEGATIVE ELEMENT

EX 03

nums = [-3, -1, -2]

→ -1

ALL NEGATIVE — BEST IS LEAST BAD

the array always has at least one element to choose from
values can be negative, zero, or positive, in any mix
the chosen run must be non-empty and fully contiguous, no skipping
only the best sum is reported, not the run's boundaries

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Every one of the n(n+1)/2 contiguous runs is a candidate; summing each one freshly is wasteful when a running total already holds most of what the next run needs. What's the least you'd need to remember to decide whether to extend or restart a run?

HINT 2 THE STRUCTURE

At each position ask one question: is the run ending here better off extended from what came before, or restarted from scratch here? Only the answer to that one comparison survives — nothing earlier needs remembering.

HINT 3 ONE STEP FROM THE ANSWER

Kadane's rule: cur = max(nums[i], cur + nums[i]) at every step, and best tracks the largest cur has ever been. One left-to-right pass, no lookback.

COACH'S BOARD — THE PATTERN, STEP BY STEP

KADANE'S RUNPATTERN · KADANE'S RULEnums = [1, -3, 4, -2, 2, 1, -5, 4]

-3

-2

-5

CUR · BEST

cur → 1

best → 1

STEP 1

Array [1, -3, 4, -2, 2, 1, -5, 4]. cur and best both start at the first value, 1 — a run of one is always valid.

STEP 1 / 9 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/maximum-subarray.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        cur = best = nums[0]
        for num in nums[1:]:
            cur = max(num, cur + num)
            best = max(best, cur)
        return best

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 7 LN

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        best = nums[0]
        for i in range(n):
            running = 0
            for j in range(i, n):
                running += nums[j]
                best = max(best, running)
        return best

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 10 LN

class Solution {
    public int maxSubArray(int[] nums) {
        int cur = nums[0], best = nums[0];
        for (int i = 1; i < nums.length; i++) {
            cur = Math.max(nums[i], cur + nums[i]);
            best = Math.max(best, cur);
        }
        return best;
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 10 LN

class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int best = nums[0];
        for (int i = 0; i < n; i++) {
            int running = 0;
            for (int j = i; j < n; j++) {
                running += nums[j];
                best = Math.max(best, running);
            }
        }
        return best;
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 14 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED