mediumArraysDynamic ProgrammingKadane's Algorithm

Maximum Subarray

Est. Time: 20 minTime: O(n)Space: O(1)

Description

Given an integer array `nums`, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

Examples

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

Output:6

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

Example 2 Input:nums = [1]

Output:1

Constraints

▪1 <= nums.length <= 10^5
▪-10^4 <= nums[i] <= 10^4

Hints

Hint 1Show

Brute force: check all subarrays — O(n²).

Hint 2Show

Can you solve it in one pass?

Hint 3Show

Kadane's Algorithm: track the current subarray sum. If it goes negative, reset to 0.

Starter Code

Solution.py

1def max_subarray(nums: list[int]) -> int:
2    # Your code here
3    pass

Solution

Solve the problem first before reviewing the solution!

Up Next

Climbing Stairs

Back to Python Problems