首页 > 试题广场 >

不相邻最大子序列和

[编程题]不相邻最大子序列和
  • 热度指数：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
冷风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)
Java
花落梦里头像 花落梦里 
    public long subsequence (int n, int[] array) {
        if(n==1) return array[0];
        long[]dp=new long[n];
        dp[0]=array[0];
        dp[1]=Math.max(dp[0],array[1]);
        for(int i=2;i<n;i++){
            dp[i]=Math.max(dp[i-1],dp[i-2]+array[i]);
        }//不相邻的话，取i-1就不能要i元素，要i元素就可以加上i-2的最大值
        return dp[n-1];
    }

发表于 2021-03-28 16:28:23 回复(1)
三201802281729969头像 三201802281729969
题目应该补充所有数组元素非负4, [-1, -1, -1,3]
发表于 2021-03-20 21:42:00 回复(2)
木析头像 木析
[JAVA] 动态规划，将一维数组简化为两个数 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型一维数组 长度为n的数组
     * @return long长整型
     */
    public long subsequence (int n, int[] array) {
        int res=0;
        int a=0,b=0;//因为dp[i]只与dp[i-1]和dp[i-2]有关，所以分别定义两个数表示dp[i-1]和dp[i-2];
        for(int x:array) {
            int c=Math.max(a+x,b);//相当于dp[i]=max(dp[i-1],dp[i-2]+array[i]);
            a=b;
            b=c;
        }
        return b;
    }
}


发表于 2021-03-14 20:36:01 回复(0)
Java
阿尼亚瓦库瓦库头像 阿尼亚瓦库瓦库 
import java.util.*;


public class Solution {
    // 动态规划解决不相邻最大子序列和
    public long subsequence (int n, int[] array) {
        
        if (array.length == 0) {
            return 0;
        }
        
        if (array.length == 1) {
            return array[0];
        }
        
        int[] dp = new int[n];
        
        // 为遍历作初始化准备
        dp[0] = array[0];
        
        if (array[0] < array[1]) {
            dp[1] = array[1];
        } else {
            dp[1] = array[0];
        }
        
        // 思路： 如果第i项为负数，直接取前一项的值；
        // 如果前i-2项子序列大小 + array[i] 大于 前i-1项子序列大小 ，就取前者，否则就取后者
        // 最后dp数组最后一个元素就是最大值了
        for (int i = 2; i < array.length; i++) {
            if (array[i] < 0) {
                dp[i] = dp[i - 1];
            } else {
                dp[i] = Math.max(dp[i - 2] + array[i], dp[i - 1]);
            }
        }
        return dp[n - 1];
    }
}
滚动数组： 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型一维数组 长度为n的数组
     * @return long长整型
     */
    public long subsequence (int n, int[] array) {
        // write code here
        if (array == null || n == 0) {
            return 0;
        }
        
        int f = 0, s = 0, res = 0;
        
        for (int a : array) {
            if (a < 0) {
                res = s;
            } else {
                res = Math.max(f + a, s);
            }
            
            // 滚动
            f = s;
            s = res;
        }
        
        return res;
    }
}
编辑于 2021-07-25 22:22:14 回复(1)
w浩头像 w浩 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型vector 长度为n的数组
     * @return long长整型
     */
    long long subsequence(int n, vector<int>& array) {
        // write code here
        int pre = 0;//记录前一个结果,空间上做下优化
        int res = 0;
        
        if(n<=0){
            return 0;
        }
        res = array[0];
        for(int i=1;i<n;i++){
            int tmp = res;
            res = max(res,pre+array[i]);
            pre = tmp;
        }
        return res;
        }
    
};

发表于 2021-04-17 23:08:50 回复(1)
C/C++
breeze_blows头像 breeze_blows
跟LeetCode打家劫舍的题一样https://leetcode-cn.com/problems/house-robber/
由于相邻的值不能选，所以
当前状态=max（上上个状态+当前值，上个状态）
同时注意好边界值即可 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型vector 长度为n的数组
     * @return long长整型
     */
    long long subsequence(int n, vector<int>& array) {
        // write code here
        if(array.size() == 0){
            return 0;
        }
        long long prep = 0, pre = array[0];
        for(int i = 1; i < n; ++i){
            long long tmp = pre;
            pre = max(prep+array[i], pre);
            prep = tmp;
        }
        return pre;
    }
};


编辑于 2021-06-01 11:26:20 回复(3)
强大的茶叶蛋不放弃头像 强大的茶叶蛋不放弃
import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型一维数组 长度为n的数组
     * @return long长整型
     */
    public long subsequence (int n, int[] array) {
        int a = 0, b = 0;
        for(int x : array) {
            int c = Math.max(a+x, b);
            a = b;
            b = c;
        } 
        return b;
    }
}
发表于 2023-08-01 15:12:53 回复(0)
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)
Java
小蒙啊头像 小蒙啊
流下了么得技术的泪水哦
只会这么搞了~~~ 
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型一维数组 长度为n的数组
     * @return long长整型
     */
    public long subsequence (int n, int[] array) {
        // write code here\
        
        long[] dp = new long[n];
        dp[0] = array[0];
        if(n < 2){
            return dp[0] > 0 ? dp[0] : 0;
        }
        dp[1] = Math.max(dp[0],array[1]);
        for(int i = 2 ; i < n ; i++){
            dp[i] = Math.max(dp[i-1],dp[i-2]+array[i]);
        }
        return dp[n-1] > 0 ? dp[n-1] : 0;
    }
}


发表于 2022-02-20 17:40:41 回复(0)
YenneferofVengerberg头像 YenneferofVengerberg 
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算
     * @param n int整型 数组的长度
     * @param array int整型vector 长度为n的数组
     * @return long长整型
     */
    #define LL long long
    long long subsequence(int n, vector<int>& array) 
    {
        // write code here
        // 事先判断和准备
        if(n == 0)
            return 0;
        if(n == 1)
            return std::max(0, array[0]);
        vector<LL> States(n, 0);
        //States[0] = array[0];
        States[0] = std::max(0, array[0]);
        States[1] = std::max(States[0], array[1]* 1LL);
        // 套公式
        for(int i = 2; i<n; i++)
        {
            States[i] = std::max(States[i-1], States[i-2] + array[i]);
        }
        return States[n-1];
    }
};

发表于 2022-02-19 20:12:10 回复(0)
Andronie头像 Andronie 
class Solution:
    def subsequence(self , n: int, array: List[int]) -> int:
        # write code here
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = array[0]
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + array[i - 1])
        return max(dp)

发表于 2021-12-29 15:25:15 回复(0)
Go
优雅且疯狂头像 优雅且疯狂 
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)
Java
雷欧尼桑头像 雷欧尼桑 
public long subsequence (int n, int[] array) {
    long[] resArr = new long[n + 2];
    resArr[0] = resArr[1] = 0;
    for (int i = 2; i < n + 2; i++) {
        long elem1 = resArr[i - 1];
        long elem2 = resArr[i - 2] + array[i - 2];
        resArr[i] = (elem1 > elem2) ? elem1 : elem2;
    }
    return resArr[n + 1];
}

发表于 2021-11-07 18:21:37 回复(0)
include<cc>头像 include<cc>
这是啥勾吧题，我看了5分钟才知道返回值是 和最大的子序列
发表于 2021-11-05 14:33:16 回复(0)
acechen15头像 acechen15 
class Solution:
    def subsequence(self , n , array ):
        # write code here
        # dp[0]是用来控制边界情况的，有可能array[0]是负数
        dp = [0] * (n + 1)
        dp[0] = 0
        dp[1] = max(dp[0], array[0])
        for i in range(2, n + 1):
            dp[i] = max(dp[i - 1], dp[i - 2] + array[i - 1])
        return dp[-1]

发表于 2021-08-25 00:00:18 回复(0)
Java
六分之三头像 六分之三
3,[1,11,3] 的结果是？
发表于 2021-08-19 23:40:52 回复(0)
Java
merlinssea头像 merlinssea 
 public long subsequence (int n, int[] array) {
        // write code here
        long choosen = array[0];
        long notChoosen = 0;
        for(int i=1;i<array.length;i++){
            long temp = Math.max(choosen,notChoosen);
            choosen = notChoosen+array[i];
            notChoosen = temp;
        }
        return Math.max(choosen,notChoosen);
    }

发表于 2021-08-12 17:08:37 回复(0)
Python
奋斗的习习张头像 奋斗的习习张 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 计算
# @param n int整型 数组的长度
# @param array int整型一维数组 长度为n的数组
# @return long长整型
# 打家劫舍
class Solution:
    def subsequence(self , n , array ):
        # write code here
        if not n:
            return 0
        if n <= 2:
            return max(max(array), 0)
        dp = []
        dp.append(max(array[0], 0))
        dp.append(max(max(array[:2]), 0))
        for i in range(2, len(array)):
            dp.append(max(dp[i-1], dp[i-2]+array[i]))
        return dp[-1]
    

发表于 2021-08-07 13:09:19 回复(0)
Java
菲尼克斯弗兰克头像 菲尼克斯弗兰克 
// 动态规划 优化一下空间复杂度
public class Solution {
    public long subsequence (int n, int[] array) {
        if (n == 1) return Math.max(0, array[0]);
        long pre = 0, now = array[0], tmp = 0;
        for (int i = 1; i < n; i++) {
            tmp = now;
            now = Math.max(pre + array[i], now);
            if (now < 0) now = 0;
            pre = tmp;
        }
        return now;
    }
}

发表于 2021-08-06 12:38:26 回复(0)
提交观点

问题信息

动态规划
难度：
40条回答 4578浏览

热门推荐

通过挑战的用户

相关试题

不相邻最大子序列和

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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