Why my code is showing TLE for some test cases? How to optimise this code?

#1

Although I have used 2 D DP, still it is showing TLE

#2

#include <bits/stdc++.h>
#define ll long long
#define pb push_back

using namespace std;

ll dp[10001][10001];

ll solve(ll i, ll j, vector v)
{
if(i>j)
return 0;
if(i==j)
return v[i];
if(j==i+1)
return max(v[i],v[j]);

if(dp[i][j]!=-1)
    return dp[i][j];
ll op1 = v[j]+min(solve(i,j-2,v),solve(i+1,j-1,v));
ll op2 = v[i]+min(solve(i+1,j-1,v),solve(i+2,j,v));
return dp[i][j] = max(op1,op2);

}

int32_t main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

ll t,n,i,j,ans;

cin>>n;
vector <ll> v(n);
for(i=0;i<n;i++)
{
    cin>>v[i];
}
for(i=0;i<n;i++)
    for(j=0;j<n;j++)
    dp[i][j]=-1;
ans = solve(0,n-1,v);
cout<<ans<<endl;

return 0;

}

#3

Hello @abhi542136 just pass your vector by reference.
it will pass all the test cases then:
check this :

#4

Yeah passed all test cases now… but can you explain why passing the vector in function without by reference is showing TLE

#5

@abhi542136 everytime you are passing the vector it is first copying all the elements again and again and thats why the time complexity for it is getting n^2 in that.

#6

ok got it… thank you…

#7

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.

#8

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.