首页 > 试题广场 >

不相邻最大子序列和

[编程题]不相邻最大子序列和
  • 热度指数：13305 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给你一个数组，其长度为 n  ，在其中选出一个子序列，子序列中任意两个数不能有相邻的下标（子序列可以为空），求该序列的最大子序列和。

本题中子序列指在数组中任意挑选若干个数组成的数组。

数据范围：，数组中所有数的值满足
进阶：空间复杂度 ， 时间复杂度
示例1

输入

3,[1,2,3]

输出

4

说明

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

输入

4,[4,2,3,5]

输出

9

说明

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

输入

1,[-1]

输出

0

说明

选择子序列为空最优
示例4

输入

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

输出

11

说明

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

备注:
输入的值在int范围内
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

动态规划
难度：
0条回答 4603浏览

热门推荐

通过挑战的用户

相关试题

不相邻最大子序列和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号