最开始使用递归DP解,stack overflow。化简了一些,复杂度为O(n)就过了。
#include <stdio.h> int main() { int case_n, n;
int i, j, tmp;
int beg, end, sum, max_sum;
int number; scanf("%d", &case_n); for (i=; i<=case_n; i++) {
scanf("%d", &n); beg = ;
tmp = ;
end = ;
sum = ;
max_sum = -;
for (j=; j<n; j++) {
scanf("%d", &number); sum += number;
if (sum > max_sum) {
max_sum = sum;
beg = tmp;
end = j;
}
if (sum < ) {
sum = ;
tmp = j+;
}
} printf("Case %d:\n", i);
printf("%d %d %d\n", max_sum, beg+, end+); if (i != case_n)
printf("\n");
} return ;
}