Maximum Subarray

EasyArrays

Open on LeetCodeAmazonAppleGoogleMicrosoft

Given an array of integers (which may contain negatives), find the contiguous subarray with the largest sum and return that sum. A subarray is a non-empty run of consecutive elements.

Input format (stdin): the first line has n. The second line has n integers. Output the maximum subarray sum.

Examples

Input: 9 -2 1 -3 4 -1 2 1 -5 4

Output: 6

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

Input: 1 -3

Output: -3

With one element the answer is that element.

Constraints

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

Sheets

Blind 75Grind 75Love Babbar 450NeetCode 150NeetCode 250Striver A2Z

maximum-subarray.cpp3 sample tests

Loading editor

Test results

Run the sample tests to check your solution against expected output.

Custom input (stdin)

Output

Run your code to see its output.