Smart robber from algorithm section

#1

// I dont have much idea of dp can you please find why 1 test case is failing

int a[1000000];
int dp[1000000];
int n,i;

int solve(int idx){

if(idx>=n){
	return 0;
}
if(dp[idx]!=0){
	return dp[idx];
}

int sum1 = a[idx] + solve(idx+2);
int sum2 = solve(idx+1);

dp[idx] = max(sum1,sum2);

return max(sum1,sum2);

}

int main() {

int t;
cin>>t;
while(t--){
	cin>>n;
	for(i=0;i<n;i++){
		cin>>a[i];
	}
	cout<<solve(0)<<endl;
	memset(a,0,sizeof(a));
	memset(dp,0,sizeof(dp));
}
return 0;

}

#2

Hey @talhashamim001
I checked the testcases and the code implemented in the backend
You code is completely correct except for the fact that it will result in overflow so use long long
Also the code implemented in backend is not using long long and resulting in overflow and hence that test case is failing
I will get it rectified soon.

#3

ok thank you…

1 Like
#4

Hey @talhashamim001
Now that testcase is removed
u can resubmit ur code to score 100/100 :slight_smile:
Marking this as resolved :slight_smile:

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#6

ok thank you…

1 Like