没有三个连续的最大子序列和

Question

给定一个正数序列，找出不存在三个连续元素的最大和。

Examples :

Input 1: arr[] = {1, 2, 3}
Output: 5
We can't take three of them, so answer is
2 + 3 = 5

Input 2: arr[] = {3000, 2000, 1000, 3, 10}
Output: 5013 
3000 + 2000 + 3 + 10 = 5013

Input 3: arr[] = {100, 1000, 100, 1000, 1}
Output: 2101
100 + 1000 + 1000 + 1 = 2101

Input 4: arr[] = {1, 1, 1, 1, 1}
Output: 4

Input 5: arr[] = {1, 2, 3, 4, 5, 6, 7, 8}
Output: 27

Input 6: arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
Output: 40

#include<bits/stdc++.h>
using namespace std;
 
int findMax(vector<int>& nums, int k, vector<long long int>& dp) 
{   
        if(k >= nums.size()) {
            return 0;
        }
        if(dp[k]!=-1)
            return dp[k];
        int a=findMax(nums,k+1,dp);                    //exclude first element
        int b=nums[k]+findMax(nums,k+2,dp);            //exclude second element
        int c=nums[k]+nums[k+1]+findMax(nums,k+3,dp);  //exclude third element
        dp[k]= max(a,max(b, c));
        return dp[k];
}

int main()
{
    vector<int>nums = {1, 2, 3, 4, 5, 6, 7, 8};
    int n = nums.size();
    vector<long long int>dp(n,-1);
    
    cout<<findMax(nums,0,dp);
    
    return 0;
}

有人能告诉我这段代码有什么错误吗？输入 1 到 5 运行完全没问题。但是，第六个测试用例的输出是 134 而不是 40。为什么会这样？

Answer 1

当 k == nums.size() - 1 时，您的 UB 具有使用 c 计算进行的越界访问。

你要处理的情况，例如：

int findMax(std::vector<int>& nums, std::size_t k, std::vector<long long int>& dp) 
{
    if(k >= nums.size()) {
        return 0;
    }
    if(dp[k] != -1)
        return dp[k];
    int a = findMax(nums,k+1,dp);                    //exclude first element
    int b = nums[k] + findMax(nums, k + 2, dp);            //exclude second element
    int c = (k + 1 < nums.size()) ? nums[k] + nums[k + 1] + findMax(nums, k + 3, dp) : 0;  //exclude third element
    dp[k] = std::max({a, b, c});
    return dp[k];
}

Demo

没有三个连续的最大子序列和

Maximum subsequence sum such that no three are consecutive

c++

arrays

c++11

recursion

dynamic-programming