Dynamic Programming Selling Wine | Wine Shelf

 Wine Shelf

You have a collection of NN wines placed next to each other on a shelf. Let's number the wines from left to right as they are standing on the shelf with integers from 1 to N, respectively. The price of the ithith wine is PiPi (prices of different wines can be different).

Because the wines get better every year, supposing today is the year 1, on year YY the price of the ithith wine will be Y∗PiY∗Pi, that is YY times the value of wine that current year.

You want to sell all the wines you have, but you want to sell exactly one wine per year, starting this year. One more constraint - each year you are allowed to sell only either the leftmost or the rightmost wine on the shelf and you are not allowed to reorder the wines on the shelf (i.e. they must stay in the same order as they are in the beginning).

You want to find out, what is the maximum profit you can get, if you sell the wines in optimal order. Since profit can be really large, report profit modulo 109+7109+7.





1≤N≤8001≤N≤800



1≤Pi≤8001≤Pi≤800
INPUT

The first line contains a single integer NN - number of wine bottles on the shelf.

The next line contains NN space separated integers PiPi, for 1≤i≤N1≤i≤N.
OUTPUT

Output a single integer - maximum profit you can make selling wines in some order modulo 109+7109+7.
EXAMPLE

Sample 1 INPUT:
properties
4 1 4 2 3


Sample 1 OUTPUT:
text
29

#include <bits/stdc++.h>
using namespace std;
#define int            long long int
#define F              first
#define S              second
#define pb             push_back
#define si             set <int>
#define vi             vector <int>
#define pii            pair <int, int>
#define vpi            vector <pii>
#define vpp            vector <pair<int, pii>>
#define mii            map <int, int>
#define mpi            map <pii, int>
#define spi            set <pii>
#define endl           "\n"
#define sz(x)          ((int) x.size())
#define all(p)         p.begin(), p.end()
#define double         long double
#define que_max        priority_queue <int>
#define que_min        priority_queue <int, vi, greater<int>>
#define bug(...)       __f (#__VA_ARGS__, __VA_ARGS__)
#define print(a)       for(auto x : a) cout << x << " "; cout << endl
#define print1(a)      for(auto x : a) cout << x.F << " " << x.S << endl
#define print2(a,x,y)  for(int i = x; i < y; i++) cout<< a[i]<< " "; cout << endl
inline int power(int a, int b)
{
  int x = 1;
  while (b)
  {
    if (b & 1) x *= a;
    a *= a;
    b >>= 1;
  }
  return x;
}
template <typename Arg1>
void __f (const char* name, Arg1&& arg1) { cout << name << " : " << arg1 << endl; }
template <typename Arg1, typename... Args>
void __f (const char* names, Arg1&& arg1, Args&&... args)
{
  const char* comma = strchr (names + 1, ',');
  cout.write (names, comma - names) << " : " << arg1 << " | "; __f (comma + 1, args...);
}
const int N = 1e9+7;
int dp[800][800];
int helper(int l,int r,vector<int>&v,int year){
    if(l>r)return 0;
    if(dp[l][r]!=0)return dp[l][r];
    dp[l][r]=max((year*v[l]+helper(l+1,r,v,year+1))%N,(year*v[r]+helper(l,r-1,v,year+1))%N);
    // cout<<dp[l][r]<<endl;
    return dp[l][r];
}
void solve() {
int n;
cin>>n;
vi v(n);
for (int i = 0; i < n; i++)
{
    cin>>v[i];
}
cout<<helper(0,n-1,v,1)%N;
}
int32_t main()
{
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  clock_t z = clock();
  int t = 1;
//   cin >> t; 
  while (t--) solve();


  return 0;
}