53. Maximum SubarrayMedium

Maximum Subarray

MediumArrayDivide and ConquerDynamic Programming·AmazonMicrosoftGoogle

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input:nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:6

The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input:nums = [1]

Output:1

Example 3:

Input:nums = [5,4,-1,7,8]

Output:23

Constraints:

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Hints

Hint 1A brute force checks all subarrays. Can you do it in one pass?▼

Consider every subarray [i,j] and compute its sum — O(n²). But do you need to keep going if the running sum becomes negative?

Hint 2If the current subarray sum is negative, what should you do?▼

If your running sum drops below zero, it can't contribute positively to any future subarray. Just reset it to 0 (start fresh from the next element).

Hint 3Kadane's: track two values — currentSum and maxSum.▼

At each position: currentSum = max(num, currentSum + num). maxSum = max(maxSum, currentSum). This gives O(n) time, O(1) space.

🌐 Real-World Analogy

Stock Portfolio Maximizer

A trading algorithm scanning daily returns needs to find the contiguous window of days that maximizes total portfolio gain. Kadane's algorithm runs this in O(n) — one pass over millions of data points. If the cumulative return dips negative, the algorithm resets its window, just like abandoning a losing streak and starting fresh. This single-pass efficiency is critical in high-frequency trading systems where every millisecond matters.

Optimal Approach — Kadane's Algorithm

O(n) Time

📈

Single Pass — Track curSum & maxSum

Time O(n)Space O(1)

Kadane's algorithm maintains a running subarray sum. The key insight: if curSum ever goes negative, it can only hurt future sums — so we discard it and start fresh.

1Initialize maxSum = nums[0] (handles all-negative arrays), curSum = 0.
2For each num in nums: if curSum < 0, reset curSum = 0.
3Add num to curSum.
4Update maxSum = max(maxSum, curSum).
5Return maxSum after the loop.

By resetting curSum to 0 whenever it goes negative, we guarantee we're always starting fresh subarrays at the best possible position. This achieves O(n) with O(1) extra space.

Array

Running Values { curSum → maxSum }

READY—

Press ▶ or step forward to begin.

i—

num—

curSum—

maxSum—

✓

—

Array

Space Play/Pause·←→ Step·R Reset

Executing Code

def maxSubArray(nums):

    maxSum = nums[0]

    curSum = 0

    for num in nums:

        if curSum < 0:

            curSum = 0

        curSum += num

        maxSum = max(maxSum, curSum)

    return maxSum

Discussion

…

Loading comments…

LeetMotion

Maximum Subarray

MediumArrayDivide and ConquerDynamic Programming·AmazonMicrosoftGoogle

Given an integer array nums, find the subarray with the largest sum, and return its sum.

Example 1:

Input:nums = [-2,1,-3,4,-1,2,1,-5,4]

Output:6

The subarray [4,-1,2,1] has the largest sum 6.

Example 2:

Input:nums = [1]

Output:1

Example 3:

Input:nums = [5,4,-1,7,8]

Output:23

Constraints:

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Hints

Hint 1A brute force checks all subarrays. Can you do it in one pass?▼

Consider every subarray [i,j] and compute its sum — O(n²). But do you need to keep going if the running sum becomes negative?

Hint 2If the current subarray sum is negative, what should you do?▼

If your running sum drops below zero, it can't contribute positively to any future subarray. Just reset it to 0 (start fresh from the next element).

Hint 3Kadane's: track two values — currentSum and maxSum.▼

At each position: currentSum = max(num, currentSum + num). maxSum = max(maxSum, currentSum). This gives O(n) time, O(1) space.

🌐 Real-World Analogy

Stock Portfolio Maximizer

Optimal Approach — Kadane's Algorithm

O(n) Time

📈

Single Pass — Track curSum & maxSum

Time O(n)Space O(1)

Kadane's algorithm maintains a running subarray sum. The key insight: if curSum ever goes negative, it can only hurt future sums — so we discard it and start fresh.

1Initialize maxSum = nums[0] (handles all-negative arrays), curSum = 0.
2For each num in nums: if curSum < 0, reset curSum = 0.
3Add num to curSum.
4Update maxSum = max(maxSum, curSum).
5Return maxSum after the loop.

By resetting curSum to 0 whenever it goes negative, we guarantee we're always starting fresh subarrays at the best possible position. This achieves O(n) with O(1) extra space.

Array

Running Values { curSum → maxSum }

READY—

Press ▶ or step forward to begin.

i—

num—

curSum—

maxSum—

✓

—

Array

Space Play/Pause·←→ Step·R Reset

Executing Code

def maxSubArray(nums):

    maxSum = nums[0]

    curSum = 0

    for num in nums:

        if curSum < 0:

            curSum = 0

        curSum += num

        maxSum = max(maxSum, curSum)

    return maxSum