Optimal game stategy 2 hackerblocks

#1

Tell me why tle occur in mycode
#include
using namespace std;
long long int optimalGame( long long int arr[], long long int i, long long int j){
if(i > j){
return 0;
}

long long int result;
	long long int first = arr[i] + min(optimalGame(arr,i+2,j),optimalGame(arr,i+1,j-1));
	long long int last = arr[j] + min(optimalGame(arr,i+1,j-1),optimalGame(arr,i,j-2));

result = max(first,last);
return result;

}
int main() {
long long int n;
cin>>n; long long int arr[n];

for(	long long int i = 0;i < n;i++){
    cin>>arr[i];
}

cout<<optimalGame(arr,0,n-1)<<endl;

return 0;

}

1 Like
#2

hi @kshitiz.gzb
you need to use dp(dynamic programming approach) to remove tle in your code

#3

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.

#4

why we use min instead of max here
long long int last = arr[j] + min(optimalGame(arr,i+1,j-1),optimalGame(arr,i,j-2));