Big O Practice: Max Subarray Kadane

def max_subarray(nums):
    best = current = nums[0]
    for x in nums[1:]:
        current = max(x, current + x)
        best = max(best, current)
    return best

Variables

• n - length of the input array nums

Explanation

Kadane scans once, keeping a single running best - **O(n)** time, **O(1)** space. The naive O(n²) brute force becomes linear once you notice the running max only needs the previous endpoint, not all of them.

More Big O practice problems · Today's daily problem