There is a array.In that Array either you can take first two element
,first and last element or alst two element ....and remove those element
you have a P-value ...P-value represnet that the score you can remove is fixed every time
means the starting score what you have removed must be carray forwarded
score is the sum of 2 element you remove you remove ....what is the maximum no of element
you can remove ?
solutin:
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int f(int i,int j,int flag,vector&arr,int sum,vector<vector<vector>>&dp){
if(i>=j)return 0;
if(dp[i][j][flag]!=-1)return dp[i][j][flag];
int firsttwo = 0;
int lasttwo = 0;
int firstlast = 0;
if(i+1<arr.size() && arr[i] + arr[i+1] == sum){
firsttwo = 1 + f(i+2,j,flag,arr,sum,dp);
}
if(arr[i] + arr[j] == sum){
firstlast = 1 + f(i+1,j-1,flag,arr,sum,dp);
}
if(j>=0 && arr[j] + arr[j-1] == sum){
lasttwo = 1 + f(i,j-2,flag,arr,sum,dp);
}
return dp[i][j][flag] = max({firsttwo,lasttwo,firstlast});}
int solution(vector &arr){
int n = arr.size();
vector<vector<vector<int>>>dp(n,vector<vector<int>>(n,vector<int>(3,-1)));
int sum1 = arr[0] + arr[n-1];
int sum2 = arr[0] + arr[1];
int sum3 = arr[n-1] + arr[n-2];
int ans1 = f(0,n-1,0,arr,sum1,dp);
int ans2 = f(0,n-1,1,arr,sum2,dp);
int ans3 = f(0,n-1,2,arr,sum3,dp);
int res = max(ans1,max(ans2,ans3));
return res;}
void solve(){
int n;
cin>>n;
vector<int> arr(n);
for(int i=0;i<n;i++){
cin>>arr[i];
}
cout<<solution(arr)<<endl;}
signed main(){
solve();}
Comments (2)