Question

Google | OA | Ronnie and Donnie | Set - 28 | IIT | 2022

Answer 1

Image of problem : 

Answer 2

Video Solution :

#include <bits/stdc++.h>

using namespace std;
typedef long long int ll ;
ll a[200005];
ll n;
map<pair<ll,ll>,pair<ll,ll>> dp1,dp2;
//dp1===donniiieeeee====>first..second
//dp2====roniiiie{i,j}--->first...second
pair<ll,ll> r(ll i,ll j);
pair<ll,ll> d(ll i,ll j);

pair<ll,ll> r(ll i,ll j){

    if(dp2.find({i,j})!=dp2.end()){
        //it already exists
        return dp2[{i,j}] ;
    }

    if(i==j){
        pair<ll,ll> d1 ;
        d1.first = 0;
        d1.second = a[i] ;
        dp2[{i,j}] = d1 ;
        return d1 ;
    }

    pair<ll,ll> d1,d2 ;
    d1.first =  d(i+1,j).first ;
    d1.second = d(i+1,j).second + a[i] ;
  

    d2.first = d(i,j-1).first ;
    d2.second = d(i,j-1).second + a[j] ;

    if(a[i]>a[j]){

        dp2[{i,j}] = d1 ;
        return d1 ;
    } else if(a[i]==a[j]){

         if((d1.first-d1.second)>=(d2.first-d2.second)){

        dp2[{i,j}] = d1 ;
        return d1 ;
    }
  

    dp2[{i,j}] = d2 ;
    return d2 ;
      

    }
  

    dp2[{i,j}] = d2 ;
    return d2 ;

}

pair<ll,ll> d(ll i,ll j){

    if(dp1.find({i,j})!=dp1.end()){
        //it already exists
        return dp1[{i,j}] ;
    }

    if(i==j){
        pair<ll,ll> d1 ;
        d1.first = a[i];
        d1.second = 0 ;
        dp1[{i,j}] = d1 ;
        return d1 ;
    }

    pair<ll,ll> d1,d2 ;
    d1.first = a[i] + r(i+1,j).first ;
    d1.second = r(i+1,j).second ;
  

    d2.first = a[j] + r(i,j-1).first ;
    d2.second = r(i,j-1).second ;

    if((d1.first-d1.second)>=(d2.first-d2.second)){

        dp1[{i,j}] = d1 ;
        return d1 ;
    }
  

    dp1[{i,j}] = d2 ;
    return d2 ;

}

int main() {
  

    ll n;
    cin>>n;
    ll i = 1 ;
    while(i<=n){
        cin>>a[i];
        i++;
    }
    pair<ll,ll> kk = d(1,n);

    cout<<kk.first<<" "<<kk.second ;
  
  
  
  

    return 0 ;
}