Given an integer array nums, find the subarray with the largest sum, and return its sum. Kadane's Algorithm: At each position, decide whether to extend the current subarray or start fresh. If the current sum becomes negative, reset it — a negative prefix only hurts us.

The step-through player is coming for this one. Two Sum has the full animation today; the rest are being authored in the admin.

Pythontime O(n) · space O(1)

def maxSubArray(nums: list[int]) -> int:
    cur_sum = max_sum = nums[0]
    for num in nums[1:]:
        # Extend current or start fresh
        cur_sum = max(num, cur_sum + num)
        max_sum = max(max_sum, cur_sum)
    return max_sum

Next upBinary Tree Level Order

Two Sum is free. Enroll to unlock every visualization and save where you stopped.Enroll free

Watch the video walkthrough