← All Problems⏱ 0:00
p-2000
Maximum Subarray
Given an integer array nums, find the contiguous subarray with the largest sum and print that sum.
Input Format
Line 1: n Line 2: n space-separated integers
Output Format
Print one integer: the maximum subarray sum.
Constraints
- 1 <= n <= 20000
- -10^4 <= nums[i] <= 10^4
Examples
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Explanation
The best subarray is [4, -1, 2, 1].
Hints
Hint 1
Hint 2
Code
>
Input
Expected Output
6
The best subarray is [4, -1, 2, 1].
Run uses the currently selected testcase. Submit always evaluates your code against the full hidden test suite from the database.