首页 > 试题广场 >

不相邻最大子序列和

[编程题]不相邻最大子序列和
  • 热度指数：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范围内
算法知识视频讲解
添加回答
Python 3
JSFaner头像 JSFaner 
class Solution:
    def subsequence(self , n: int, array: List[int]) -> int:
        a,b = 0,0
        for i in range(n):
            a,b = b,max(a+array[i],b)
        return b 

发表于 2022-02-25 11:03:41 回复(0)
Python 3
冷风tt头像 冷风tt
用两个全局变量来记录前面和的最大。
pre_max表示与当前arr[i]不相邻的最大和。初始化为arr[0]
cur_max表示与当前arr[i]相邻的最大和。初始化为arr[1]
从i=2开始遍历，先更新当前最大cur_max, 再更新前面最大。每次向后移动时重复的更迭pre_max，cur_max。
最后cur_max就是要的结果。
class Solution:
    def subsequence(self , n , array ):
        # write code here
        if n == 0:
            return 0
        if n < 2:
            return array[0]
        pre_max = max(0, array[0])
        cur_max = max(0, array[1])
        for i in range(2, n):
            cur = max(pre_max, 0) + array[i]
            pre_max = max(pre_max, cur_max)
            cur_max = max(cur_max, cur)
        return cur_max

编辑于 2021-07-26 17:27:17 回复(0)
Python 3
HHHChen77头像 HHHChen77
python 动态规划 打家劫舍问题 
class Solution:
    def subsequence(self , n , array ):
        # 类似"打家劫舍"问题：相邻位置不能同时偷
        # dp[i]定义为数组中前i个数据的最大子序列和
        dp = [0] * (n+1)
        # basecase 0/1个数最大和就是0/array[0]
        dp[1] = array[0]
        # 状态转移
        for i in range(2,n+1):
            # 面对第i个数,选择 偷 或者 不偷
            # 不偷：等同于dp[i-1]
            # 偷：前i-2个数据的序列和加第i个数据
            dp[i] = max(dp[i-1], dp[i-2] + array[i-1])
        # 返回数组中前n个数据的最大序列和
        return dp[n]



发表于 2021-07-23 13:52:49 回复(0)
提交观点

问题信息

动态规划
难度：
3条回答 4602浏览

热门推荐

通过挑战的用户

相关试题

不相邻最大子序列和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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