首页 > 代码库 > nyoj-44-子串和

nyoj-44-子串和

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\n", max);
21     }
22     return 0;

23 } 

nyoj-44-子串和