Maximum Subarray

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 best

Every 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.

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 best

Tracing nums = [-2,1,-3,4,-1,2,1,-5,4]:

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.