All problems

Maximum Subarray

Medium · greedy

Given a list of integers nums, find the contiguous block of one or more items whose sum is the largest, and return that sum.

The block must contain at least one number. That means if every number is negative, the answer is the single largest (least negative) number, not 0.

Examples

Example 1

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

Output: 6

The block [4, -1, 2, 1] sums to 6, and no other block does better.

Example 2

Input: nums = [5]

Output: 5

A single number is a valid block.

Example 3

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

Output: -1

Every block is negative, and the best one is just [-1].

Constraints