給定一個正數序列，找出不存在三個連續元素的最大和。
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。為什么會這樣？
uj5u.com熱心網友回復：
當 時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];
}
演示
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/469968.html
上一篇：根據使用次數隨機選擇單詞
下一篇：在類的兩個物件之間使用阻塞佇列