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;
}