2. Maximum Subarray Sum
MediumArrayDynamic ProgrammingKadane
Find the contiguous subarray (containing at least one number) with the largest sum and print that sum.
Input format
Line 1: n Line 2: n integers
Output format
The maximum subarray sum.
Example 1
Input
9 -2 1 -3 4 -1 2 1 -5 4
Output
6
Explanation: The subarray [4, −1, 2, 1] has the largest sum, 6.
Example 2
Input
1 1
Output
1
Explanation: A single element is the only subarray.
Constraints
1 ≤ n ≤ 10⁵ −10⁴ ≤ values ≤ 10⁴
Read input from standard input and print the answer to standard output. Your code is judged against 6 test cases, most of them hidden.
Loading the MyLoginn IDE…