https://practice.geeksforgeeks.org/problems/optimal-strategy-for-a-game-1587115620/1/#
Hi friends, I was solving this question on gfg. But on 100th test case my solution is showing segmentation error.
Even after many hours I am not able to find out what is the problem with my code.
Could anyone please help me here.
Code:
class Solution{
public:
#define ll long long int
#define pi pair<ll,ll>
long long maximumAmount(int arr[], int n){
// Your code here
pi dp[n][n];
for(ll i=0;i<n;i++){
dp[i][i]={arr[i],0};
}
ll j1=1;
while(j1<n){
ll i=0,j=j1;
while(j<n){
ll a=arr[i]+dp[i+1][j].second;
ll b=arr[j]+dp[i][j-1].second;
if(a>b){
dp[i][j]={a,dp[i+1][j].first};
}
else{
dp[i][j]={b,dp[i][j-1].first};
}
i++,j++;
}
j1++;
}
return dp[0][n-1].first;
}
};
Approach used:
I have made 2D dp array and I am storing values in pairs in that array.
The first value in the pair represents the sum if the first turn is made. The second value in a pair represents the sum if the second turn is taken.
By keeping the values of smaller subarrays the final value would be dp[0][n-1].