最大子序列总和使得没有三个是连续的

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