Maximum subarray (Kadane)

Classic linear DP.

dp arrays kadane

Implement `max_subarray(nums: list[int]) -> int`.

Return the maximum sum of any non-empty contiguous subarray.

Constraints

1 ≤ len(nums) ≤ 10^5. Values can be negative.

Example

>>> max_subarray([-2,1,-3,4,-1,2,1,-5,4])
6

25 points ~20 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Kadane: curr = max(x, curr+x); global = max(global, curr).

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.