测试时间：14:00-16:30 16:30之后提交的程序一概不收
提交方式不变
问题名称 最大和 修剪花卉 金字塔 文件名 sum makeup pyramid 输入文件 sum.in makeup.in pyramid.in 内存限制均为256M
输出文件 sum.out makeup.out pyramid.out 时限 分值 1s 100 1s 100 1s 100 最大和(max)
题目描述;
N个数围成一圈，要求从中选择若干个连续的数（注意每个数最多只能选一次）加起来，问能形成的最大的和。
输入格式：
第一行输入N，表示数字的个数，第二行输入这N个数字。
输出格式：
输出最大和。
样例输入： 8
2 -4 6 -1 -4 8 -1 3 样例输出： 14
数据说明： 40% 1<=N<=300 60% 1<=N<=2000
100% 1<= N<=100000,答案在longint范围内。
修剪花卉
程序名：makeup.* 时间限制：1秒 输入：makeup.in 内存限制：32M 输出：makeup.out 问题背景：
ZZ对数学饱有兴趣，并且是个勤奋好学的学生，总是在课后留在教室向老师请教一些问题。 一天他早晨骑车去上课，路上见到一个老伯正在修剪花花草草，顿时想到了一个有关修剪花卉的问题。
于是当日课后，ZZ就向老师提出了这个问题：
一株奇怪的花卉，上面共连有N 朵花，共有N-1条枝干将花儿连在一起，并且未修剪时每 朵花都不是孤立的。
每朵花都有一个“美丽指数”，该数越大说明这朵花越漂亮，也有“美丽指数”为负数的， 说明这朵花看着都让人恶心。
所谓“修剪”，意为：去掉其中的一条枝条，这样一株花就成了两株，扔掉其中一株。 经过一系列“修剪“之后，还剩下最后一株花（也可能是一朵）。 老师的任务就是：通过一系列“修剪”（也可以什么“修剪”都不进行），使剩下的那株（那 朵）花卉上所有花朵的“美丽指数”之和最大。
老师想了一会儿，给出了正解（交大的老师是很牛的~）。ZZ见问题被轻易攻破，相当不爽， 于是又拿来问你。
输入说明：
第一行一个整数N(1 ≤ N ≤ 16000)。表示原始的那株花卉上共N 朵花。
第二行有N 个整数，第I个整数表示第I朵花的美丽指数。
接下来N-1行每行两个整数a,b，表示存在一条连接第a 朵花和第b朵花的枝条。 输出说明：
一个数，表示一系列“修剪”之后所能得到的“美丽指数”之和的最大值。保证绝对值不超 过2147483647。 样例输入： 7
-1 -1 -1 1 1 1 0 1 4 2 5 3 6 4 7 5 7 6 7
样例输出： 3
数据范围：
对于 60%的数据， 保证N≤1,000 对于100%的数据，保证N≤16,000
金字塔(pyramid)
题目描述：
小X来到一个雄奇的金字塔挖宝，但是这是一座被诅咒的金字塔，小X必须马上逃离这里，否则小X就会被埋在金字塔里，但他不希望此行落空。
现在小X面前有N+1种财宝，每种财宝都有一个价值。第一种财宝重量为0，第二种财宝重量为1，总之第I种财宝重量为I-1。现在小X希望拿走N+M个物品，但是这M+N个物品总重量不能超过N。小X希望能获得最大的价值。你能帮帮他吗？ 由于金字塔跟小X一样牛，所以每种财宝无限个。
输入格式：
第一行两个正整数N，M
第二行N+1个整数，第I个整数代表了第I种财宝的价值
输出格式：
一个数，表示最大利润。
样例输入： 5 3
4 7 2 5 -3 6
样例输出： 47
数据范围：
10%满足N,M<=10
40%满足N,M<=100
100%满足 N,M<=3000 abs(财宝价值)<=1000