我要招人

去企业版

首页 > 试题广场 >

不相邻最大子序列和

[编程题]不相邻最大子序列和

热度指数：13301 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给你一个数组，其长度为 n ，在其中选出一个子序列，子序列中任意两个数不能有相邻的下标（子序列可以为空），求该序列的最大子序列和。

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

数据范围： $1 \le n \le 10^5$ ，数组中所有数的值满足 $|val| \le 2147483647$

进阶：空间复杂度 $O(1)$ ，时间复杂度 $O(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范围内

算法知识视频讲解

OfferCall！

发表于 2021-03-16 11:35:13

其实就是一个打家劫舍的问题，数组中每一个元素值就是可以偷的金额，相邻的不能偷，求能够偷出的最大金额是多少。设置一个状态转移数组dp，dp[i]表示数组中前i个元素所能偷的最大金额是多少状态转移表达式： (1)对于当前的元素arr[i],如果偷，那么dp[i] = dp[i-2] + arr 展开全文

王清楚

发表于 2021-03-30 12:30:22

表示区间的不相邻最大子序列和，那就是我们要找的答案了。如果取的话，就不能取了，这个情况下的不相邻最大子序列和为如果不取的话，的不相邻最大子序列和为所以 c++ class Solution { public: long long subsequence(i 展开全文

abdd_

发表于 2021-03-17 00:52:36

看到这题，很容易观察到这是一个包含子问题的，直接dp。题目要求是不相邻的子序列值。什么样子会帮助满足最大呢？1，序列包含尽可能多的数2，序列包含尽可能大的数。考虑不相邻的话，要不要加入第i个数，需要考虑的问题是它前一个i-1 要不要加入，至于i-2则不需要考虑，因为加入第i个数必然可以加入不展开全文

有名

发表于 2021-07-30 22:07:55

描述给你一个n,，和一个长度为n的数组，在不同时选位置相邻的两个数的基础上，求该序列的最大子序列和（挑选出的子序列可以为空）。方法一思路枚举，递归，回溯；所求子序列集合要求各个元素之间互不相邻，假设所给数组为arr，对于下标为index的元素总共两种选择，将其放入子序列集合或者是不放入，展开全文

youxiwang

发表于 2022-01-16 09:08:53

JAVA - DP Solution, O(n) time, O(1) space 请输出不相邻最大子序列和递归逻辑 f(0) = max(array[0], 0); f(1) = max(array[1], 0); f(2) = max(array[2], 0) + max(f(0)); 展开全文

叩思

发表于 2022-01-04 21:33:19

可以参考动态规划的打家劫舍问题。代码超过78%的用户代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可计算 @param n int整型数组的长度 @param array int整型一维数组长度为n的数组 @return long长整型 class Soluti 展开全文

叩思

发表于 2022-01-04 21:35:45

# # 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 # # 计算 # @param n int整型数组的长度 # @param array int整型一维数组长度为n的数组 # @return long长整型 # class Solution: &nb 展开全文

WALTQ

发表于 2021-08-04 21:55:11

代码中有说明 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算 * @param n int整型数组的长度 * @param array int整型vec 展开全文

B612_2024

发表于 2021-12-03 18:51:04

public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算 * @param n int整型数组的长度 * @param array int整型vector 长度为n的数组 * @retu 展开全文

我和我

发表于 2022-01-01 17:47:48

public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 计算 * @param n int整型数组的长度 * @param array int整型一维数组长度为n的数展开全文

问题信息

动态规划

难度：

40条回答 113收藏 3904浏览

通过挑战的用户

小燕子2019...

2022-10-28 00:33:52
牛客82468...

2022-09-21 21:23:37
雨眠和顽固

2022-09-15 14:33:29
牛客45553...

2022-09-13 19:54:11
沉稳的查理起床了

2022-09-10 15:35:02

不相邻最大子序列和

输入

输出

说明

输入

输出

说明

输入

输出

说明

输入

输出

说明

备注:

问题信息

热门推荐

通过挑战的用户

相关试题