Maximum Subarray 25 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

LeetCode #53: Maximum Subarray — your first Medium problem! This introduces Kadane's Algorithm, one of the most elegant algorithms ever.

Given an array of integers, find the contiguous subarray with the largest sum.

Example:
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
The subarray [4, -1, 2, 1] has the largest sum = 6

Kadane's Algorithm — The Idea:
As you scan left to right, keep a running sum. At each element, ask: 'Should I continue the current subarray, or start fresh from here?'

💭 Your turn! Take what you learned above and write the code yourself. Struggling is part of learning! 🧠

Walk-through with [-2, 1, -3, 4, -1, 2, 1, -5, 4]:

Start: current=-2, max=-2
num=1: max(1, -2+1)=1, current=1, max=1
num=-3: max(-3, 1-3)=-2, current=-2, max=1
num=4: max(4, -2+4)=4, current=4, max=4
num=-1: max(-1, 4-1)=3, current=3, max=4
num=2: max(2, 3+2)=5, current=5, max=5
num=1: max(1, 5+1)=6, current=6, max=6 ✓
num=-5: max(-5, 6-5)=1, current=1, max=6
num=4: max(4, 1+4)=5, current=5, max=6

Complexity: Time O(n), Space O(1). Beautiful!

📋 Instructions

Implement `maxSubArray(nums)` using **Kadane's Algorithm**. The key decision at each step: is it better to add the current element to the running subarray, or start a new subarray from the current element? `current_sum = max(nums[i], current_sum + nums[i])`

Kadane's Algorithm: Keep a running sum. If running sum goes negative, reset to 0. Track the maximum sum seen. Think of it as: 'Is the current subarray helping or hurting?'

⚠️ Try solving it yourself first — you'll learn more!

def maxSubArray(nums):
    current_sum = nums[0]
    max_sum = nums[0]
    
    for i in range(1, len(nums)):
        # Either extend current subarray or start new one
        current_sum = max(nums[i], current_sum + nums[i])
        max_sum = max(max_sum, current_sum)
    
    return max_sum

🧪 Test Cases

Input

maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])

Expected

6

Test case 1

Input

maxSubArray([1])

Expected

1

Edge case — single element

Input

maxSubArray([5, 4, -1, 7, 8])

Expected

23

Test case 3

← Previous Next Exercise →

main.py

Hi! I'm Rex 👋

Output

Ready. Press ▶ Run or Ctrl+Enter.

›