← 返回 bytedance 的题目列表Maximum Subarray Sum
类型：online_judge
Given an integer array nums of length n (values may be negative), return the maximum possible sum of a non-empty contiguous subarray.
Input Format
Line 1: integer n
Line 2: n integers (can be positive or negative)
Output Format
Output a single integer: the maximum subarray sum.
Constraints
1 <= n <= 2 * 10^5
-10^9 <= nums[i] <= 10^9
Example
Example 1:
Input:
9
-2 1 -3 4 -1 2 1 -5 4
Output:
6
Example 2:
Input:
1
-5
Output:
-5
Example
Input
9
-2 1 -3 4 -1 2 1 -5 4
Output
6