OI题库

【问题描述】
     给一串整数 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