Maximum Subarray

The key idea

At each index decide whether to extend the current running subarray or start fresh from this element: take cur = max(num, cur + num). Track the best cur ever seen. A prefix only helps the future if its running sum stays positive; the moment it would drag the next element down, drop it and restart.

Problem

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

A subarray is a contiguous, non-empty sequence of elements within nums.

Constraints

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

Examples

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

Input: nums = [1] Output: 1

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

Complexity

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

See the full solution

✓Full worked approach
✓Reference code in 5 languages
✓Problem-solving tips
✓Step-by-step animated visualization

410310

Step-by-step visualization

Start free →