问题1753--最大子段和（分治法）

1753: 最大子段和（分治法）

[命题人 : ]
时间限制 : 1 sec  内存限制 : 128 MB

提交
解决: 227提交量: 315统计

题目描述

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

输入

第一行是一个整数，表示序列的长度 n。
第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai。

输出

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

样例输入 Copy 

7
2 -4 3 -1 2 -4 3

样例输出 Copy 

4

提示

选取 [3, 5] 子段 {3,−1,2}，其和为 4。
对于 100% 的数据，保证1≤n≤2×1e5，−1e4≤ai≤1e4。

来源/分类

 
提交