问题描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

格式

输入

第一行输入数组长度 第二行数据元素

输出

最大子序列和

样例

5
-2 1 -3 4 -1

4

样例2

3
1 2 3

6

提示

解释1: 连续子数组 [4] 的和最大，为 4。
解释2: 连续子数组 [1, 2, 3] 的和最大，为 6。