Brute Force
Time O(n²)Space O(1)For every starting index, extend the subarray one element at a time and track the running total, updating the best sum seen anywhere.
class Solution: def maxSubArray(self, nums: list[int]) -> int: n = len(nums) best = float('-inf') for i in range(n): total = 0 for j in range(i, n): total += nums[j] best = max(best, total) return bestEvery subarray sum is computed independently — O(n²) work in total, and it never reuses the fact that a sum ending at j-1 tells you almost everything about a sum ending at j.
Kadane's Algorithm
OptimalTime O(n)Space O(1)For a subarray ending exactly at index i, the best possible sum is either nums[i] alone, or nums[i] plus whatever the best sum ending at i-1 was — if that previous best is negative, it can only hurt you, so drop it and restart from nums[i]. Track that “best sum ending here” as you scan, and keep a running maximum of it.
class Solution: def maxSubArray(self, nums: list[int]) -> int: best = float('-inf') cur = 0 for num in nums: cur = max(num, cur + num) best = max(best, cur) return bestPlay the trace below: at every index watch the two candidate sums under extend and restart, and which one the algorithm keeps.
Decision at index 0
Restarting wins — the previous run is dropped.
cur · best ending here
-2
nums[0..0]
best · answer so far
-2
nums[0..0]
At index 0, extend gives 0 + -2 = -2 and restart gives -2. The tie goes to restart, so the run starts here. Now cur = best = -2.
Why it’s correct: at every index we ask one local question — “does carrying the previous run forward help or hurt?” — and a negative running sum can never help a future sum, so dropping it loses nothing. Complexity: one pass, two running variables → O(n) time, O(1) space.