不相邻最大子序列和

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

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

算法知识视频讲解

优雅且疯狂

package main
func subsequence( n int ,  array []int ) int64 {
    // write code here
    if len(array)<2{
        return max(0,int64(array[0]))
    }
	dp := make([]int64, n)

	dp[0] = max(0,int64(array[0]))
	dp[1] = max(dp[0],int64(array[1]))
	for i:=2;i<n;i++{
		dp[i] = max(dp[i-1],dp[i-2]+int64(array[i]))
	}
	return dp[n-1]
}

func max(a,b int64)int64{
	if a>b {
		return a
	}
	return b
}

发表于 2021-12-23 12:40:58 回复(0)