求子序列

成绩 0 开启时间 2013年01月15日 星期二 11:05
折扣 0.8 折扣时间 2013年01月15日 星期二 11:05
允许迟交 关闭时间 2013年01月15日 星期二 11:05
输入文件 subq.in 输出文件 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