I had been trying to solve these problem from last three hours but I am not able to find where my code is giving tle . Please help to find where I am wrong.
Here is code updated code as per your suggestions :
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
int main() {
// your code goes here
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
int n;
cin>>n;
vector<ll>arr;
for(int i=0;i<n;i++)
{
ll num;
cin>>num;
arr.push_back(num);
}
vector<ll>dp(10001);//max no of monsters
if(n == 0)
{
printf("Case %d: %d\n",i,0);
continue;
}
dp[0] = 0;//case when there are no monster
dp[1] = arr[0];//case when is there is only one monster
//dp[2] = max(arr[1]+dp[0],dp[1]);
for(int i=2;i<=n;i++)
{
dp[i] = max(arr[i-1]+dp[i-2],dp[i-1]);//select the maximum one
}
printf("Case %d: %lld\n",i,dp[n]);
}
return 0;
}
Can u plz provide test cases where it is failing?
Edit : Thank you @akshitm16 my solution is accepted