求子序列

Grade 0 Open Time Tuesday, 15 January 2013, 4:05 pm
Discount 0.8 Time Discount Tuesday, 15 January 2013, 4:05 pm
Allow late Yes Close Time Tuesday, 15 January 2013, 4:05 pm
Input file subq.in Output file subq.out

【问题描述】
     给一串整数 a [1… n ] ,求出它和最大的子序列,即找出 1<= i <= j <= n ,使 a [ i ]+ a [ i +1]+…+ a [ j-1 ]+ a [ j ] 最大。

【输入格式】
    文件的第一行为一个正整数n

第二行有n个整数,-32768 ≤ a[i] ≤ 32767

【输出格式】
   输出文件第一行有一个整数j,表示子序列的起始位置编号。

第二行有一个整数j,表示子序列的终止位置编号。

第三行有一个数,是子序列的和。

注:若有多个解,只输出i值最小的解,若多个解i值相同,则输出j值最小的解。

【输入输出样例】
 
输入:
subq.in
5
-2 2 5 -1 6

输出:
subq.out
2
5
12

数据范围:

对于30%的数据,n<=100

对于60%的数据,n<=400

对于100%的数据,n<=1,000,000