最大子数组和

题号：NC229297
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

给定一个长度为 $n$ （ $1≤n≤10^5$ ）的整数数组 $a_1,a_2,a_3...,a_n$ $(-1000≤a_i≤1000)$ ,现在请你找出该数组的一个子数组，使得这个子数组的元素和最大

选择的子数组长度不能为0

第一行包含一个整数 $n$ ，表示数组的长度

第二行包含 $n$ 个整数 $a_1,a_2,...,a_n$ ，表示数组

输出为一个整数表示答案

示例1

复制

7
2 -4 3 -1 2 -4 3

复制

显然，选择子数组，其总和最大，答案为4