Given a sequence of positive numbers, find the maximum sum that can be formed which has no three consecutive elements present.
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;
}
Can somebody tell me what is the error with this code? Input 1 to 5 is running perfectly fine. But, the output for the sixth test case is coming as 134 instead of 40. Why is it so?
CodePudding user response：
When k == nums.size() - 1, you have UB with out of bound access with c computation.
You have to handle the case, for example:
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];
}