Job-A-Thon 21 Q2

/*
Problem Statement

Given an array "arr" of positive integers with length N, your goal is to achieve the maximum possible score by removing elements from either the beginning or the end of the array. The score for removing an element is calculated as:

    Score = element * length(arr) + minimum(arr)

Here, "arr" is considered before the current operation, and you can choose to remove elements from the start or end of the array.
"element" represents the value of the removed element.

TC 1:
N = 3
arr = {2,3,4}
Output: 26
Explanation: A possible way to perform the operations
-> remove 4 from last,
score = 4*length({2,3,4})+min({2,3,4}) = 14
updated arr = {2,3}

-> remove 2 from start,
score = 2*length({2,3})+min({2,3}) = 6
updated arr = {3}

-> remove last element 3,
score = 3*length({3})+min({3}) = 6

-> total score = 14 + 6 + 6 = 26
*/


class Solution
{
    public:
    int min_in_range(int l,int r,vector<vector<int>>& m,vector<int>& logg)
    {
        int length=(r-l+1),k;
        k=logg[length];
        return min(m[l][k],m[r-(1<<k)+1][k]);
    }

    long long func(int l, int r, int n, vector<int>& arr, vector<vector<int>>& m,vector<int>& logg,vector<vector<long long>>& dp){
        if(n==1){
            return (2*arr[l]);
        }

        if(dp[l][r]!=-1){
            return dp[l][r];
        }

        long long val1=((arr[l]*n + min_in_range(l,r,m, logg)) + func(l+1,r,n-1,arr,m,logg,dp));
        long long val2=((arr[r]*n + min_in_range(l,r,m,logg)) + func(l,r-1,n-1,arr,m,logg,dp));
        return dp[l][r]=max(val1,val2);
    }

    long long MaxScore(int N, vector<int>&arr)
    {
        if(N==1){
            return 2*arr[0];
        }

        int l=0,r=N-1,len=N;
        vector<vector<int>>m(20005,vector<int>(16));
        vector<int>logg(20005);
        vector<vector<long long>>dp(N+2,vector<long long>(N+2,-1));

        logg[1]=0;
        for(int i=2;i<20005;i++){
            logg[i]=logg[i/2]+1;
        }
        for(int i=0;i<N;i++){
            m[i][0]=arr[i];
        }

        for(int j=1;j<16;j++){
            for(int i=0;(i+(1<<j)-1)<N;i++){
                m[i][j]=min(m[i][j-1],m[i+(1<<(j-1))][j-1]);
            }
        }

        long long ans=func(l,r,len,arr,m,logg,dp);
        return ans;
    }
};