不相邻最大子序列和_牛客题霸

给你一个数组，其长度为 n ，在其中选出一个子序列，子序列中任意两个数不能有相邻的下标（子序列可以为空），求该序列的最大子序列和。本题中子序列指在数组中任意挑选若干个数组成的数组。数据范围：，数组中所有数的值满足进阶：空间复杂度，时间复杂度

示例1

输入

3,[1,2,3]

有[],[1],[2],[3],[1,3] 4种选取方式其中[1,3]选取最优，答案为4

示例2

4,[4,2,3,5]

其中[4,5]的选取方案是在满足不同时选取相邻位置的数的情况下是最优的答案

示例3

1,[-1]

选择子序列为空最优

示例4

5,[3,2,3,4,5]

其中选择[3,3,5]的方案是最优的答案

输入的值在int范围内