#61 · Greedy

Maximum Subarray

Given an integer array, find the contiguous non-empty subarray with the largest sum and return that sum.

MediumLeetCode

Active
Found
Window
Visited
Rejected

Speed1×step 1 / 1

Pointers

Variables

Hash map / table

Stack / queue

Foundations & data-structure selection

Running best-ending-here (Kadane)

Keep the best sum of a subarray that ends at the current element. If the run so far is negative it cannot help any extension, so drop it and start fresh at the current element. The answer is the best such value seen.

Memory layout

Two numbers: current and best.

Operation	Cost
time	O(n)
space	O(1)

Segment summary (total, prefix, suffix, best)

A segment can be summarised by four numbers, and two adjacent summaries combine in O(1): total adds, best prefix and suffix may extend across the join, and the best subarray is either in one half or crosses the middle. This is divide and conquer, and it also parallelises.

Memory layout

Four integers per segment and a recursion stack of depth log n.

Operation	Cost
time / space	O(n) / O(log n)

Why it fits

A subarray is a contiguous range, and the best subarray ending at i either extends the best one ending at i − 1 or starts at i. That local choice is optimal, which is exactly what makes a greedy / one-pass method correct.
A negative running sum is dead weight: any extension is better without it, so discarding it never loses the optimum.
Summaries of adjacent segments combine in constant time, giving a divide-and-conquer alternative that is useful for range queries and parallel processing.

Why alternatives degrade

Taking all positive numbers:: The subarray must be contiguous, so a negative number between two positives cannot simply be skipped.
Sorting:: Sorting destroys the contiguity and the order that define a subarray.
Prefix sums with a double loop:: It is correct (best = max over j of prefix[j] − min earlier prefix) but the naive double loop is still O(n²); only the running minimum makes it linear, which is Kadane in disguise.

Four approaches, from naive to production

1 · beginner

Every subarray, sum recomputed

time O(n³)space O(1)

Try every pair (i, j), add up nums[i..j] with an inner loop and keep the largest sum.

int maxSubArray(vector<int>& nums) {
    int best = nums[0];
    for (int i = 0; i < (int)nums.size(); i++) {
        for (int j = i; j < (int)nums.size(); j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) sum += nums[k];
            best = max(best, sum);
        }
    }
    return best;
}

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

def max_sub_array(nums):
    best = nums[0]
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            total = 0
            for k in range(i, j + 1): total += nums[k]
            best = max(best, total)
    return best

function maxSubArray(nums: number[]): number {
  let best = nums[0];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      let sum = 0;
      for (let k = i; k <= j; k++) sum += nums[k];
      best = Math.max(best, sum);
    }
  }
  return best;
}

Flaws & bottlenecks

Re-adds almost the same elements for neighbouring subarrays.
Three nested loops: unusable beyond a few hundred elements.
Starting best at 0 would be wrong for all-negative arrays (this code starts at nums[0]).

Interviewer cross-questions

What is repeated?

Say: The sum of [i..j + 1] is the sum of [i..j] plus one more element, but it is recomputed from scratch.

What about arrays with only negative numbers?

Say: The answer is the largest (least negative) element, because the subarray must be non-empty. Initialising best to 0 would wrongly return 0.

How do you remove the inner loop?

Say: Keep a running sum while extending j.

2 · intermediate

Running sum from each start

time O(n²)space O(1)

For each start i, extend j one element at a time keeping a running sum and update the best after each step.

int maxSubArray(vector<int>& nums) {
    int best = nums[0];
    for (int i = 0; i < (int)nums.size(); i++) {
        int sum = 0;
        for (int j = i; j < (int)nums.size(); j++) {
            sum += nums[j];
            best = max(best, sum);
        }
    }
    return best;
}

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

def max_sub_array(nums):
    best = nums[0]
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            best = max(best, total)
    return best

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

Flaws & bottlenecks

Still quadratic: each start re-walks the rest of the array.
Ignores that a prefix with a negative sum can never be part of an optimal subarray.
Slow for arrays of 100,000 elements.

Interviewer cross-questions

Why is a negative-sum prefix never worth keeping?

Say: If the part before position p sums to less than zero, a subarray that starts after it is strictly better than one that includes it. So after a negative running sum, start again.

What is the complexity?

Say: n starts, up to n extensions each: n(n + 1)/2 steps.

How do you do it in one pass?

Say: Kadane's algorithm: restart the running sum whenever it becomes worse than starting at the current element.

3 · advanced

Kadane's algorithm

time O(n)space O(1)

Scan once keeping current = the best sum of a subarray ending here: either the element alone or the previous current plus the element. Track the maximum current as the answer.

int maxSubArray(vector<int>& nums) {
    int best = nums[0], current = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        current = max(nums[i], current + nums[i]);
        best = max(best, current);
    }
    return best;
}

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

def max_sub_array(nums):
    best = current = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

function maxSubArray(nums: number[]): number {
  let best = nums[0], current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

Flaws & bottlenecks

It returns the sum only; reporting the subarray needs the start index tracked separately.
It must start from nums[0], not 0, to be correct for all-negative inputs.
It is inherently sequential, so it does not parallelise directly.

Interviewer cross-questions

Why is it correct?

Say: Every optimal subarray ends somewhere. The best subarray ending at i is either [i] alone or the best ending at i − 1 extended by i; taking the max covers both. The answer is the best over all end positions.

How do you also return the subarray?

Say: Remember where the current run started (reset it when you restart) and, whenever best improves, copy start and the current index.

Is this greedy or dynamic programming?

Say: Both views are valid: current[i] = max(nums[i], current[i − 1] + nums[i]) is a DP recurrence, and discarding a negative run is the greedy choice that justifies keeping only one number.

4 · expert

Divide and conquer with segment summaries

time O(n)space O(log n) recursion

Split the array at the middle, solve both halves and combine four numbers per half: total, best prefix, best suffix and best subarray. The best subarray is in the left half, in the right half, or crosses the middle (best suffix of the left plus best prefix of the right).

int maxSubArray(vector<int>& nums) {
    function<array<int, 4>(int, int)> solve = [&](int lo, int hi) -> array<int, 4> {
        if (lo == hi) return {nums[lo], nums[lo], nums[lo], nums[lo]};
        int mid = (lo + hi) >> 1;
        auto left = solve(lo, mid), right = solve(mid + 1, hi);
        int total = left[0] + right[0];
        int prefix = max(left[1], left[0] + right[1]);
        int suffix = max(right[2], right[0] + left[2]);
        int best = max({left[3], right[3], left[2] + right[1]});
        return {total, prefix, suffix, best};
    };
    return solve(0, (int)nums.size() - 1)[3];
}

public int maxSubArray(int[] nums) {
    return solve(nums, 0, nums.length - 1)[3];
}
private int[] solve(int[] nums, int lo, int hi) {
    if (lo == hi) return new int[]{nums[lo], nums[lo], nums[lo], nums[lo]};
    int mid = (lo + hi) >> 1;
    int[] left = solve(nums, lo, mid), right = solve(nums, mid + 1, hi);
    int total = left[0] + right[0];
    int prefix = Math.max(left[1], left[0] + right[1]);
    int suffix = Math.max(right[2], right[0] + left[2]);
    int best = Math.max(left[3], Math.max(right[3], left[2] + right[1]));
    return new int[]{total, prefix, suffix, best};
}

def max_sub_array(nums):
    def solve(lo, hi):
        if lo == hi: return [nums[lo]] * 4
        mid = (lo + hi) >> 1
        left, right = solve(lo, mid), solve(mid + 1, hi)
        total = left[0] + right[0]
        prefix = max(left[1], left[0] + right[1])
        suffix = max(right[2], right[0] + left[2])
        best = max(left[3], right[3], left[2] + right[1])
        return [total, prefix, suffix, best]
    return solve(0, len(nums) - 1)[3]

function maxSubArray(nums: number[]): number {
  const solve = (lo: number, hi: number): number[] => {
    if (lo === hi) return [nums[lo], nums[lo], nums[lo], nums[lo]];
    const mid = (lo + hi) >> 1;
    const left = solve(lo, mid), right = solve(mid + 1, hi);
    const total = left[0] + right[0];
    const prefix = Math.max(left[1], left[0] + right[1]);
    const suffix = Math.max(right[2], right[0] + left[2]);
    const best = Math.max(left[3], right[3], left[2] + right[1]);
    return [total, prefix, suffix, best];
  };
  return solve(0, nums.length - 1)[3];
}

Flaws & bottlenecks

More code and more arithmetic than Kadane for the same answer on a single array.
Allocates a small array per call (a struct or tuple would avoid that).
The recursion is an overhead unless you need the parallelism or range queries.

Interviewer cross-questions

Why use it when Kadane is simpler?

Say: Segment summaries combine associatively. That gives parallel processing (each chunk is summarised independently), a segment tree for "best subarray in range [l, r]" queries with updates, and map-reduce style computation.

What is the recurrence?

Say: T(n) = 2T(n/2) + O(1) because combining two summaries is constant time, so T(n) = O(n). If the crossing case were computed by scanning outwards from the middle it would be O(n) per level and O(n log n) overall.

Why do we need prefix and suffix?

Say: A subarray crossing the middle is a suffix of the left half joined with a prefix of the right half. Knowing only the best of each half is not enough for this case.

Synchronized code walkthrough

Showing: Every subarray, sum recomputed — shares the player above; click any step to jump.

int maxSubArray(vector<int>& nums) {
    int best = nums[0];
    for (int i = 0; i < (int)nums.size(); i++) {
        for (int j = i; j < (int)nums.size(); j++) {
            int sum = 0;
            for (int k = i; k <= j; k++) sum += nums[k];
            best = max(best, sum);
        }
    }
    return best;
}

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

def max_sub_array(nums):
    best = nums[0]
    for i in range(len(nums)):
        for j in range(i, len(nums)):
            total = 0
            for k in range(i, j + 1): total += nums[k]
            best = max(best, total)
    return best

function maxSubArray(nums: number[]): number {
  let best = nums[0];
  for (let i = 0; i < nums.length; i++) {
    for (let j = i; j < nums.length; j++) {
      let sum = 0;
      for (let k = i; k <= j; k++) sum += nums[k];
      best = Math.max(best, sum);
    }
  }
  return best;
}

int maxSubArray(vector<int>& nums) {
    int best = nums[0];
    for (int i = 0; i < (int)nums.size(); i++) {
        int sum = 0;
        for (int j = i; j < (int)nums.size(); j++) {
            sum += nums[j];
            best = max(best, sum);
        }
    }
    return best;
}

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

def max_sub_array(nums):
    best = nums[0]
    for i in range(len(nums)):
        total = 0
        for j in range(i, len(nums)):
            total += nums[j]
            best = max(best, total)
    return best

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

int maxSubArray(vector<int>& nums) {
    int best = nums[0], current = nums[0];
    for (int i = 1; i < (int)nums.size(); i++) {
        current = max(nums[i], current + nums[i]);
        best = max(best, current);
    }
    return best;
}

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

def max_sub_array(nums):
    best = current = nums[0]
    for i in range(1, len(nums)):
        current = max(nums[i], current + nums[i])
        best = max(best, current)
    return best

function maxSubArray(nums: number[]): number {
  let best = nums[0], current = nums[0];
  for (let i = 1; i < nums.length; i++) {
    current = Math.max(nums[i], current + nums[i]);
    best = Math.max(best, current);
  }
  return best;
}

int maxSubArray(vector<int>& nums) {
    function<array<int, 4>(int, int)> solve = [&](int lo, int hi) -> array<int, 4> {
        if (lo == hi) return {nums[lo], nums[lo], nums[lo], nums[lo]};
        int mid = (lo + hi) >> 1;
        auto left = solve(lo, mid), right = solve(mid + 1, hi);
        int total = left[0] + right[0];
        int prefix = max(left[1], left[0] + right[1]);
        int suffix = max(right[2], right[0] + left[2]);
        int best = max({left[3], right[3], left[2] + right[1]});
        return {total, prefix, suffix, best};
    };
    return solve(0, (int)nums.size() - 1)[3];
}

public int maxSubArray(int[] nums) {
    return solve(nums, 0, nums.length - 1)[3];
}
private int[] solve(int[] nums, int lo, int hi) {
    if (lo == hi) return new int[]{nums[lo], nums[lo], nums[lo], nums[lo]};
    int mid = (lo + hi) >> 1;
    int[] left = solve(nums, lo, mid), right = solve(nums, mid + 1, hi);
    int total = left[0] + right[0];
    int prefix = Math.max(left[1], left[0] + right[1]);
    int suffix = Math.max(right[2], right[0] + left[2]);
    int best = Math.max(left[3], Math.max(right[3], left[2] + right[1]));
    return new int[]{total, prefix, suffix, best};
}

def max_sub_array(nums):
    def solve(lo, hi):
        if lo == hi: return [nums[lo]] * 4
        mid = (lo + hi) >> 1
        left, right = solve(lo, mid), solve(mid + 1, hi)
        total = left[0] + right[0]
        prefix = max(left[1], left[0] + right[1])
        suffix = max(right[2], right[0] + left[2])
        best = max(left[3], right[3], left[2] + right[1])
        return [total, prefix, suffix, best]
    return solve(0, len(nums) - 1)[3]

function maxSubArray(nums: number[]): number {
  const solve = (lo: number, hi: number): number[] => {
    if (lo === hi) return [nums[lo], nums[lo], nums[lo], nums[lo]];
    const mid = (lo + hi) >> 1;
    const left = solve(lo, mid), right = solve(mid + 1, hi);
    const total = left[0] + right[0];
    const prefix = Math.max(left[1], left[0] + right[1]);
    const suffix = Math.max(right[2], right[0] + left[2]);
    const best = Math.max(left[3], right[3], left[2] + right[1]);
    return [total, prefix, suffix, best];
  };
  return solve(0, nums.length - 1)[3];
}