题目链接：1007 Maximum Subsequence Sum

思路

采用扫描一遍，时间复杂度为O(n)的算法。本题要求找到段内总和最大的连续段，思路是从最小片段开始着手，假设两段连续正数段，中间为负数，若前段与负数和仍为正数，那两段加上正数的值必然大于后段的段内总和，形如3，-2，5，三段和6大于后段和5，将5看作一个新的小段即可，逐渐累加合成大段。于是在扫描过程中，首先选择一个非负数作为起点，逐位向后扫描，直至和为负，则重新向后选择新起点。过程中发现当前和大于最大和，更新最大起点与终点，注意若相等不更新，因为题目表明相等情况取小值，此条件同样要求选择起始点时包括了0。输出时注意若一个点都没有被纳入，说明全段为负，按照题目要求输出0，全段起点，终点。 #include <iostream> using namespace std; int main(){ int K, sum = -1, start, end, a, flag = 0; int sum2 = -1, start2, end2; cin >> K; for(int i = 0; i < K; i++){ cin >> a; if(!i) start = a; //选择头结点 if(!flag){ if(a>=0){ start = a; end = a; sum = a; flag = 1; } } //选择尾结点 else{ if(sum + a >= 0){ end = a; sum += a; } else flag = 0;//加入尾结点后变成负数则重新选择头节点 } //更新最大值 if(sum > sum2){ sum2 = sum; start2 = start; end2 = end; } } if(sum2 == -1) printf("0 %d %d", start, a); else printf("%d %d %d", sum2, start2, end2); }