最大子段和

题目描述

给出一个长度为 $n$ 的序列 $a$，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 $n$。

第二行有 $n$ 个整数，第 $i$ 个整数表示序列的第 $i$ 个数字 $a_i$。

输出格式

输出一行一个整数表示答案。

输入样例 #1

7
2 -4 3 -1 2 -4 3

输出样例 #1

4

说明/提示

样例 1 解释

选取 $[3, 5]$ 子段 $\{3, -1, 2\}$，其和为 $4$。

输入样例 #2

45
-222673446 527354090 847385317 -149273239 318483280 749336783 570612265 162298040 408438478 500485848 987480697 -974659669 -692641778 -42326763 843347165 18032678 646166704 -925600314 670060461 -526969679 674518502 597675130 60257347 983702217 507330911 -664236160 -594004268 208352593 -785157776 166044691 479544687 -152155849 -636562035 -399398721 785395335 403864600 775888279 -947277900 924470587 783197752 412431323 734430723 -958126884 -741353357 -877313700

输出样例 #2

8256322332

输入样例 #3

50
442018101 -587306840 356960403 -761024663 -527085113 92789446 719982406 -709052248 -479150493 -67877725 -197966285 -890291078 699872614 838825411 -598372765 -697671953 362094661 -35518064 -795694809 -259590189 -586715567 -824856097 651311422 259922175 255802045 -160545252 183127219 -536723263 245771160 -370587335 -569059826 -275854393 -882470756 744513821 786165955 312199805 57141445 479362685 -568893417 -598443481 801639374 -656131530 -555873319 966696999 846932950 731248822 -363110456 -390013059 -296650455 488543990

输出样例 #3

3346560109

数据规模与约定

• 对于 $40\%$ 的数据，保证 $n \leq 2 \times 10^3$。
• 对于 $100\%$ 的数据，保证 $1 \leq n \leq 2 \times 10^5$，$-10^4 \leq a_i \leq 10^4$。

2026/01/21：增加一组 hack 数据。