http://acm.nyist.net/JudgeOnline/problem.php?pid=44
子串和
时间限制：5000 ms | 内存限制：65535 KB
难度：3
- 描述
- 给定一整型数列{a1,a2...,an}，找出连续非空子串{ax,ax+1,...,ay}，使得该子序列的和最大，其中，1<=x<=y<=n。
- 输入
- 第一行是一个整数N(N<=10)表示测试数据的组数）
每组测试数据的第一行是一个整数n表示序列中共有n个整数，随后的一行里有n个整数I(-100=<I<=100)，表示数列中的所有元素。(0<n<=1000000) - 输出
- 对于每组测试数据输出和最大的连续子串的和。
- 样例输入
1 5 1 2 -1 3 -2
- 样例输出
5
- 提示
- 输入数据很多,推荐使用scanf进行输入
解题思路：经典的动态规划题目,但我的方法没用-_-|||
1 #include<stdio.h>
2
3 int main()
4 {
5 int t, j, l, max, n, x;
6 scanf("%d", &t);
7 while(t--){
8 scanf("%d", &n);
9 max=-999999;
10 for(j = 1, l = 0; j <= n; j++){
11 scanf("%d", &x);
12 l += x;
13 if(l > max){
14 max = l;
15 }
16 if(l < 0){
17 l = 0;
18 }
19 }
20 printf("%d ", max);
21 }
22 return 0;
2
3 int main()
4 {
5 int t, j, l, max, n, x;
6 scanf("%d", &t);
7 while(t--){
8 scanf("%d", &n);
9 max=-999999;
10 for(j = 1, l = 0; j <= n; j++){
11 scanf("%d", &x);
12 l += x;
13 if(l > max){
14 max = l;
15 }
16 if(l < 0){
17 l = 0;
18 }
19 }
20 printf("%d ", max);
21 }
22 return 0;
23 }