#122 Medium Time O(n) Space O(1) Animated

Maximum Subarray

Find the contiguous subarray with the largest sum (Kadane's).

LeetCode ↗

Approach: Kadane's Algorithm

Click play to start

Step 0 / 0

Press play to start the visualization.

1×

Description

Find the contiguous subarray with the largest sum (Kadane's).

Constraints

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

Solution — Kadane's Algorithm

O(n) O(1)

def maxSubArray(nums):
    res = nums[0]
    total = 0
    
    for n in nums:
        if total < 0:
            total = 0
        total += n
        res = max(res, total)
        
    return res

Jump Game

Maximum Subarray

Steps

Description

Constraints

Tags

Solution — Kadane's Algorithm