Rejudge Progress:
1027: 买花瓶(简单动态规划DP)
Time Limit: 1000 MS Memory Limit: 65536 KBTotal Submit: 1177 Accepted: 466 Page View: 3507
Submit Status Discuss
Description
john想买几个花瓶装饰一下新房。已知花店的花瓶被固定地排成一行并被依次排号，且花店有 一个原则，花瓶不能移动也不能挑选，只能买连号的花瓶。由于每个花瓶都有自己的美学价值， 请你帮john选出其中美学价值最大的一组。 比如，有六个花瓶，它们的美学价值分别是 3 -1 2 4 -6 5，那么john应该选3 -1 2 4（美学价值为8） 这一组。而不能挑2 3 4 5这一组（违犯），或是2 4组（美学价值为6，不是最大）。
Input
测试有很多次,对于每一次测试:
第一行为一个正整数 N（ 1 <= N <=10000 ），代表花瓶的个数.当N=0时,代表测试结束；
第二行的N个整数Mi( -100 <= Mi <= 100 )分别代表每个花瓶的美学价值，其间用空格分开。
Output
每次测试输出一行,代表拥有最大美学价值的一组连号花瓶的美学价值MAX。
6
3 -1 2 4 -6 5
0
8