不连续整数最大和

题目描述

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

输入

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

输出

最大一组整数和。

样例

提示

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

n \leq 5 \times 10^ 5, 数字不超过 10^6

来源

动规专题