Given a sequence of K integers { N?1??, N?2??, ..., N?K?? }. A continuous subsequence is defined to be { N?i??, N?i+1??, ..., N?j?? } where 1≤i≤j≤K. The Maximum Subsequence is the continuous subsequence which has the largest sum of its elements. For example, given sequence { -2, 11, -4, 13, -5, -2 }, its maximum subsequence is { 11, -4, 13 } with the largest sum being 20.
Now you are supposed to find the largest sum, together with the first and the last numbers of the maximum subsequence.
Input Specification:
Each input file contains one test case. Each case occupies two lines. The first line contains a positive integer K (≤10000). The second line contains K numbers, separated by a space.
Output Specification:
For each test case, output in one line the largest sum, together with the first and the last numbers of the maximum subsequence. The numbers must be separated by one space, but there must be no extra space at the end of a line. In case that the maximum subsequence is not unique, output the one with the smallest indices i and j (as shown by the sample case). If all the K numbers are negative, then its maximum sum is defined to be 0, and you are supposed to output the first and the last numbers of the whole sequence.
Sample Input:
10
-10 1 2 3 4 -5 -23 3 7 -21
Sample Output:
10 1 4
题意：给定n个数，求最大连续子段和，并输出该连续子段的第一个数和最后一个数，如果子段中的数都是负数，那么它的最大和被定义为0，就输出整个序列的第一个和最后一个数。
若最后的最大连续子段和小于0，那么则输出0。这意味着最小子段和默认为0
分析：
求最大连续子段和：设置一个变量sum，从第一个数加到最后一个数，保存过程中sum的最大值。
若过程中sum<0,那么让sum=0，含义是将当前子段的子段和为负数，那么最大的连续子段和肯定不在当前子段中，那么把当前子段丢弃掉，重新找新的子段。
每次sum<0更新sum=0时使用一个变量first记录 当前下标+1，first含义是新的子段的起始位置
求子段中的第一个数和最后一个数：设第一个数的下标为l，最后一个数的下标为r
每次更新sum时（意味着找到了子段和更大的子段），将r置为当前元素的下标，l置为first。
这里有一个坑点：
测试样例：
2
-1 0
应该输出0 0 0 而不是0 -1 0
因为题干上说了，当全部数为负数时候，才输出所有数中的第一个数和最后一个数，而0不是负数。
所以记录sum最大值的变量maxx的初始值不能设置为0,只有设置为负数，当当前元素为0时才能更新l和r。
#include<bits/stdc++.h>
int a[100000];
int main()
{int n;cin>>n;for(int i=1;i<=n;i++)cin>>a[i];int maxx=-1,l=1,r=n;int sum=0,first=1;for(int i=1;i<=n;i++){sum+=a[i];if(sum<0){sum=0;first=i+1;}else if(sum>maxx){maxx=sum;l=first;r=i;}}if(maxx<0)maxx=0;cout<<maxx<<" "<<a[l]<<" "<<a[r]<<endl;return 0;
}