2155: 多组最大子序列的和

给定由N个整数组成的序列a1, a2, ⋯ , an,编写程序得到其中最大子序列的和并输出该子序列的第一个和最后一个元素的下标。

输入包含多组测试数据。

第1行有一个数 N，表示 N 个整数。

第2行有 N 个数，第 i 个整数为 ai，每两个整数之间用一个空格隔开。

每组数据输出一行结果，包含最大子序列的和以及子序列的第一个下标i和最后一个元素的下标j。所有元素下标为0 ~ N-1。

如果最大子序列不唯一，则选择 i 最小的那个子序列，如果仍不唯一，则选择i最小的子序列中 j 最小的那个子序列。

若所有K个元素都是负数，则定义其最大和为0，输出0 0 0。

8
6 -2 11 -4 13 -5 -2 10
5
10 -10 10 -10 10
8
-1 -5 -2 3 -1 0 -2 0
4 
-1 -2 -4 -3

27 0 7
10 0 0
3 3 3
0 0 0

对于 30%的数据： 1 ≤ N ≤ 100。

对于 60%的数据： 1 ≤ N ≤ 1000。

对于 100%的数据：1 ≤ N ≤ 100000；|ai | ≤ 1000。输入最多包括10组数据。