题目大意:给出一系列的数字。要求你输出这些数字的最大连续和,并输出构成这个最大连续和的第一个数和最后一个数
解题思路:用一个变量维护最大连续和
假设当前这个变量小于0的话,就表示这个变量仅仅会拉低连续和的值了。所以将其变为0 假设当前这个变量大于0。不管它多小,最大连续和加上它都仅仅会增大而不会减小,所以不用改变这个变量 假设当前变量是0的话,就要依据题目来更新了#include#include const int N = 10010;int num[N];int n, ans_l, ans_r, ans_Max;void solve() { int Max = num[0], Sum = num[0]; int l, r; l = r = ans_l = ans_r = 0; ans_Max = Max; for(int i = 1; i < n; i++) { if(Sum < 0) { Sum = 0; l = r = i; } Sum += num[i]; r = i; if(Sum > Max) { ans_r = r; ans_l = l; Max = Sum; ans_Max = Max; } }}int main() { while(scanf("%d", &n) != EOF && n) { for(int i = 0; i < n; i++) scanf("%d", &num[i]); solve(); if(ans_Max >= 0) printf("%d %d %d\n", ans_Max, num[ans_l], num[ans_r]); else printf("0 %d %d\n", num[0], num[n - 1]); } return 0;}