题目描述

输入一个 非空 整型数组，数组里的数可能为正，也可能为负。

数组中一个或连续的多个整数组成一个子数组。

求所有子数组的和的最大值。

输入

第一行一个整数$n$

第二行一共$n$个整数

输出

求所有子数组的和的最大值。

8
1 -2 3 10 -4 7 2 -5

18

提示

$1 \leq n \leq 10^5$

$-1000 \leq 数组元素 \leq 1000$