SANPOWER-Editorial

PROBLEM LINK:

PRACTICE
Editorialist: Yogesh Yogendra

DIFFICULTY:

HARD

PREREQUISITES:

Dynamic Programming

PROBLEM:

You are given an array of candies(Arr) of size N. The power of the Santa represents the sum of the values that you obtain after performing the described operations for N times. Your task is to delete the array by performing the following operations:

∙• For any turn(i) where (1 <= i <= N), delete either of the end (first or last) elements of remaining array.

∙• Before deleting that element (let’s say at index K), it contributes to the sum of the values as Arr[K] x turn(i) + SV(i) the power of the array. Here, turn(i) represents the number of turns in which you are performing the operation

∙• SV(i) represents the value of the maximum element that is present in the remaining array before the ith turn is performed

You are required to perform this in such a way that you maximize the value of the power of the Santa.

You must print the maximum value of the power that can be obtained after the array is completely deleted.

EXPLANATION:

Here first we have to find out the maximum value for every i and j in O(N^2) and store that in an array,so that we can get the maximum value in O(1) time,and after that we have to do Dynamic Programming approach.
And in Dynamic Programming approach, we have two choices either to take first or last element so simply we will recur for both first and last element and return the maximum of both.

SOLUTION:

#include<bits/stdc++.h>
#define int long long int
using namespace std;


int maxarr[1001][1001];
int dp[1001][1001];

int func(int i,int j,int a[],int turn){
    if(i>j) return 0;
    if(dp[i][j]!=-1) return dp[i][j];

    int x = ((a[i]*turn) + maxarr[i][j]) + func(i+1,j,a,turn+1);
    int y = ((a[j]*turn) + maxarr[i][j]) + func(i,j-1,a,turn+1);
    return dp[i][j] = max(x,y);
}

int32_t main()
{   
        int n;
        cin>>n;
        int a[n];
        for(int i=0;i<n;i++) cin>>a[i];
        maxarr[n][n];
        memset(dp,-1,sizeof(dp));
        for(int i=0;i<n;i++){
            int ma = a[i];
            for(int j=i;j<n;j++){
                ma = max(ma,a[j]);
                maxarr[i][j] = ma;
            }
        }
        cout<<func(0,n-1,a,1)<<endl;
   
    
    return 0;
}

It is a very easy question in editorial it is given in the difficult way instead of dp and checking all possibilities we can do it by finding the max of the arr and then choosing the smaller one from the start and the last as if larger will be later it will contribute more as it will be multiplied by a greater turn