Maximum Subarray

LeetCode 53 • Medium • Arrays

Find the contiguous subarray with the largest sum. Return the sum. Kadane: track current_sum and max_sum; reset current_sum when it goes negative.

TimeO(n)single pass

SpaceO(1)two variables

current_sum: — max_sum: —

Input

Current subarray

Max subarray

current_sum

—

max_sum

—

Speed:

Ready

Press Play. Kadane's algorithm: for each element, either extend current_sum or reset to the element. Update max_sum when current exceeds it.

✎ Whiteboard

Size:3

⌨ Type It

Practice until you don't need to look. Use the guide comments below as scaffolding. The green highlights are the nuances to burn into memory.

# ─── MAX SUBARRAY (LeetCode 53) — Kadane's ───

# Pattern: Extend or restart at each element

# Time: O(n) Space: O(1)

# 1. Define: maxSubArray(nums)

# 2. Init with first element:

# current_sum = nums[0]

# max_sum = nums[0]

# 3. Loop from index 1:

# for i in range(1, len(nums)):

# 4. Extend or restart: current_sum = max(nums[i], current_sum + nums[i])

# 5. Track best: max_sum = max(max_sum, current_sum)

# 6. Return: return max_sum

# Vars: current_sum, max_sum, i

▼ your implementation ▼

Verify your solution: