和值最大的连续子序列

题目描述:

有n（n<=100000）个元素的序列，元素值都在[-100，100]之间的整数数列，并从中找出最大累加和的子序列（在原数列中连续）。

输入格式:

第一行一个数n 
第二行n个数

输出格式:

输出共三行
第一行最大的连续子序列和
第二行表示区间 
第三行一个连续和最大的子序列 
若有多个这样的子序列，输出最左边的

样例输入:

8
10 -20 6 8 10 -50 -10 16

样例输出:

24
3 5
6 8 10

提示:

n<=100000

子序列后面的0，不算在里面。

时间限制: 1000ms
空间限制: 128MB

---

来源: 原创