Position: All -> Works -> EOJ 1109 Max Sum | 08-03-28 22:03:40
EOJ 1113 装箱问题EOJ 1855 Expedition
Font-Size:
Large | Middle | Small

Description

给你一个序列a[1],a[2],a[3]......a[n], 你的任务是去计算这个序列中和最大的一个子序列. 例如, 给你个序列(6,-1,5,4,-7), 和最大的一个子序列是 6 + (-1) + 5 + 4 = 14.
本题目是求最大（连续）子序列的和

Input

在第一行输入一个数 T(1<=T<=20) 意思是输入序列的个数. 然后后面T行, 每行开始一个数是 N(1<=N<=100)，这个序列有N个数, 然后接下来有N个数(每个数的范围是 -1000到 1000).

Output

对每个测试，输出自序列和的最大值。

Sample Input

2
5 6 -1 5 4 -7
7 0 6 -1 1 -6 7 -5

Sample Output

14
7

Source

ECNU算法作业

C++代码
  1. #include<stdio.h>  
  2. int main() {  
  3.     int i,t,n,a[101];  
  4.     scanf("%d",&t);  
  5.     while(t--) {  
  6.         scanf("%d",&n);  
  7.         int sum = 0,ans = -99999999;;  
  8.         for(i = 0;i < n;i++) {  
  9.             scanf("%d",&a[i]);  
  10.             sum += a[i];  
  11.             if(sum > ans)  
  12.                 ans = sum;  
  13.             if(sum < 0)  
  14.                 sum = 0;  
  15.         }  
  16.         printf("%d\n",ans);  
  17.     }  
  18. }  

Tags:
最大连续子序列和,动态规划,DP
Share to:
查看文章views(835) | 查看评论view comments(1) | 添加评论add comment
EOJ 1113 装箱问题EOJ 1855 Expedition

Comments:

ghdjApr 26th, 2009 at 2:51 am
#1
经典

Add Comments: