Maximum SubarrayMedium

Maximum Subarray

Medium 33.1k50% acceptance

ArrayDynamic Programming

Given an integer array nums, find the contiguous subarray with the largest sum and return that sum. The subarray must contain at least one element.

Example 1

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

Output: 6

The subarray [4,-1,2,1] sums to 6.

Example 2

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

Output: 23

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁴ ≤ nums[i] ≤ 10⁴

Asked atAmazonMicrosoftLinkedInGoogle

JavaScript

⌘↵ to run

Loading editor…

Case 1

[-2,1,-3,4,-1,2,1,-5,4]

expected: 6

Case 2

[1]

expected: 1

Case 3

[5,4,-1,7,8]

expected: 23

Case 4

[-3,-1,-2]

expected: -1