3215 - 不连续整数最大和

给定一组整数,需要从中选择不连续的一组数字,使得和最大。

输入

第一行为数字个数n。 第二行为n个整数,数字之间用空格隔开。

输出

最大一组整数和。

样例

输入

7
1 4 3 5 2 6 8

输出

17

提示

样例1中,最大不连续整数组为4 5 8

n < 1000, 数字不超过 10^6

来源

动规专题

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题