当前没有测试数据。

Description

Given an array of n integers, your task is to find the maximum sum of values in a contiguous, nonempty subarray.

Input Format

The first input line has an integer n: the size of the array.

The second line has n integers x1,x2,…,xn: the array values.

Output Format

Print one integer: the maximum subarray sum.

8
-1 3 -2 5 3 -5 2 2

9

Hint

<li> 1≤n≤2⋅10⁵ </li> <li> −109≤x_i≤10⁹ </li>

Source

CSES