Two State Tracking While Scanning

Two state tracking keeps two running aggregates (e.g. current sum and best sum, or open count and max) while pointers move.

Try this in Python

def max_subarray(nums: list[int]) -> int:
    best = cur = nums[0]
    for x in nums[1:]:
        cur = max(x, cur + x)
        best = max(best, cur)
    return best


print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))

Key takeaways

• Kadane is one-pointer but shows paired states cur/best.
• Pair with two-pointer window lessons mentally.
• States must reset correctly on negatives.