我要招人

去企业版

首页 > 试题广场 >

不相邻最大子序列和

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

热度指数：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范围内

算法知识视频讲解

Python 3

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

用两个全局变量来记录前面和的最大。

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

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)