#include
#include <bits/stdc++.h>
using namespace std;
//reccursive
#define max 5
int max_and_print(int x , int y)
{
if( x > y)
{
cout<<" beg “<<” “;
return x;
}
else if(y > x)
{
cout<<” end “<<” ";
return y;
}
}
int max_profit( int wines[] , int first , int last , int year)
{
if( year == max+1)
{
return 0;
}
int x , y;
x = wines[first]*year + max_profit(wines , first+1 , last , year+1);
y = wines[last]*year + max_profit(wines , first , last-1 , year+1);
return max_and_print(x , y);
}
// top down dp
int dp[max+1][max][max];
int max_profit_top_down( int wines[] , int first , int last , int year)
{
if( year == max+1)
{
return 0;
}
if(dp[year][first][last] != -1)
{
cout<<“found here”<<endl;
return dp[year][first][last];
}
int x , y;
x = wines[first]*year + max_profit(wines , first+1 , last , year+1);
y = wines[last]*year + max_profit(wines , first , last-1 , year+1);
dp[year][first][last] = max_and_print(x , y);
return dp[year][first][last];
}
int main(void)
{
int wines[] = { 2, 4, 6, 2, 5};
int first = 0;
int last = max-1;
int year = 1;
memset(dp , -1 , sizeof(dp));
cout<<max_profit(wines , first , last , year)<<endl;
cout<<max_profit_top_down(wines , first , last , year)<<endl;
return 0;
}