Maximum Subarray Solution

Problem

Given an integer array, return the sum of the contiguous subarray (containing at least one element) that has the largest sum.

Example:

Input: nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
Output: 6
Explanation: The subarray [4, -1, 2, 1] sums to 6.

A counter-example: nums = [-3, -1, -2] → output -1 (not 0 — you must select at least one element, so the least-negative element is the best answer for an all-negative array).

Intuition

At each position you're making a binary choice: extend the running subarray or abandon it and start fresh. The key insight is that a negative running sum is always a liability — it can only reduce the total of anything appended after it. So whenever the accumulated sum goes negative, it's strictly better to restart from the current element.

Approach 1 — Brute Force

Try every possible contiguous subarray by iterating over all start and end index pairs, tracking the maximum sum seen.

Steps:

Initialize max_sum to nums[0] to correctly handle all-negative arrays.
For each start index left, reset current_sum to 0.
Extend the window right, adding each element to current_sum.
Update max_sum whenever current_sum exceeds it.
Return max_sum.

1def maxSubArray(nums: list[int]) -> int:
2    max_sum = nums[0]
3
4    for left in range(len(nums)):
5        current_sum = 0
6        for right in range(left, len(nums)):
7            current_sum += nums[right]
8            max_sum = max(max_sum, current_sum)
9
10    return max_sum

Time: O(n²) — two nested loops, each up to n iterations.
Space: O(1) — only scalar variables, no extra storage.

Approach 2 — Kadane's Algorithm

A single linear pass. At each element, pick the larger of starting fresh at this element versus extending the previous running sum. Track the global best seen so far.

Steps:

Initialize both current_sum and max_sum to nums[0] — handles all-negative inputs correctly.
Iterate from index 1 onward.
At each element, set current_sum = max(num, current_sum + num) — restart when the previous running sum would reduce the total.
Update max_sum if current_sum exceeds it.
Return max_sum.

1def maxSubArray(nums: list[int]) -> int:
2    current_sum = nums[0]
3    max_sum = nums[0]
4
5    for num in nums[1:]:
6        # restart if the accumulated sum would drag down this element
7        current_sum = max(num, current_sum + num)
8        max_sum = max(max_sum, current_sum)
9
10    return max_sum

Time: O(n) — single pass through the array.
Space: O(1) — two scalar variables regardless of input size.

Complexity Summary

Approach	Time	Space	When to use
Brute Force	O(n²)	O(1)	Establishing a baseline in an interview before optimizing
Kadane's Algorithm	O(n)	O(1)	Always — the standard solution for any contiguous subarray sum problem

Common Mistakes

Initializing max_sum = 0: Returns 0 for all-negative arrays like [-3, -1, -2], where the correct answer is -1. Always initialize to nums[0].
Resetting current_sum to 0 instead of the current element: current_sum = 0 discards the current element entirely on a reset, producing wrong answers when every element is negative. The correct reset is captured by max(num, current_sum + num).
Starting the loop at index 0 after initializing from nums[0]: Processing nums[0] a second time can inflate the result on inputs that start with a positive number.
Confusing this with Maximum Product Subarray: The product variant requires tracking both the running maximum and minimum because multiplying by a negative flips the sign — the simple restart logic here does not apply directly.
Assuming the answer must be positive: On all-negative inputs the answer is the largest (least negative) single element, not zero. The initialization to nums[0] and the max(num, ...) restart handle this automatically.

Maximum Subarray — Solution