czq走上了花海中的一条小道,这条小道有个观赏点,第个观赏点有的美丽值。注意美丽值可以是负数。
路过每个观赏点,czq都会观赏当地的景色。随后他可以选择步行前往第下一个观赏点,或者选择终止旅程。
czq定义这趟旅途的美丽值为沿途观赏的观赏点的美丽值之和。他可以在任何一个观赏点开始旅途,也可以在之后的任何一个观赏点结束旅途,但一旦结束旅途他就无法返回小道。如果对所有景点都不感兴趣,czq可以选择不访问任何观赏点(此时旅途的美丽值为0)。他想问你旅途的美丽值最大值为多少。
第一行一个整数,为观赏点的个数。
接下来一行有个整数,为每个观赏点的美丽值。
输出仅一个整数,为最大的美丽值。
8 -2 4 3 -1 5 -2 -7 5
11
czq的旅途:2->3->4->5