问题描述

给定 $K$ 个整数的序列 $\{ N_1, N_2, \ldots, N_K \}$，其任意连续子序列可表示为 $\{ N_i, N_{i+1}, \ldots, N_j \}$，其中 $1 \leq i \leq j \leq K$。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列 $\{ -2, 11, -4, 13, -5, -2 \}$，其最大连续子序列为 $\{ 11, -4, 13 \}$，最大和为 $20$。现在增加一个要求，即还需要输出该子序列的第一个和最后一个元素。

输入格式

测试输入包含若干测试用例，每个测试用例占 $2$ 行，第 $1$ 行给出正整数 $K$（$K \leq 10000$），第 $2$ 行给出 $K$ 个整数，中间用空格分隔，每个数的绝对值不超过 $100$。当 $K$ 为 $0$ 时，输入结束，该用例不被处理。

输出格式

对每个测试用例，在 $1$ 行里输出最大和、最大连续子序列的第一个和最后一个元素，中间用空格分隔。如果最大连续子序列不唯一，则输出序号 $i$ 和 $j$ 最小的那个（如输入样例的第 $2$、$3$ 组）。若所有 $K$ 个元素都是负数，则定义其最大和为 $0$，输出整个序列的首尾元素。

样例输入

5
-3 9 -2 5 -4
3
-2 -3 -1
0

样例输出

12 9 5
0 -2 -1

提示

这是一道稍微有点难度的动态规划题。

首先可以想到的做法是枚举每个区间的和，预处理 $sum[i]$ 来表示区间 $[1, i]$ 的和之后通过减法我们可以 $O(1)$ 时间获得区间 $[i, j]$ 的和，因此这个做法的时间复杂度为 $O(n^2)$。

然后这题的数据范围较大，因此还需作进一步优化才可以 AC。记第 $i$ 个元素为 $a[i]$，定义 $dp[i]$ 表示以下标 $i$ 结尾的区间的最大和，那么 $dp[i]$ 的计算有 $2$ 种选择，一种是含有 $a[i-1]$，一种是不含有 $a[i-1]$，前者的最大值为 $dp[i-1]+a[i]$，后者的最大值为 $a[i]$。而两者取舍的区别在于 $dp[i-1]$ 是否大于 $0$。