【HDOJ】1003 Max Sum

最开始使用递归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 ;
}
上一篇:Struts2实现文件上传和下载,多文件上传,限制文件大小,限制文件类型


下一篇:算法&数据结构系列 -- 堆(优先队列)