Problem Statement

Imagine you have a collection of N wines placed next to each other on a shelf. For simplicity, let us 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 ith wine is pi​ (prices of different wines can be different). Because the wines get better every year, supposing today is the year 1, on year y the price of the ith wine will be y*pi, i.e., y-times the value of 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 is that 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 were in the beginning).

You want to find the maximum profit you can get if you sell the wines in optimal order.

Example:

Input 1: price = [1, 4, 2, 3]
Output 1: 29
Explanation 1: The optimal solution would be to sell the wines in the order p1, p4, p3, p2 for a total profit 1 * 1 + 3 * 2 + 2 * 3 + 4 * 4 = 29.

Input 2: arr = [2, 3, 5, 1, 4]
Output 2: 50

Recursive Code

import java.io.*;

class Innoskrit {
    
    public static int solve(int price[], int start, int end, int year) {
        if(start > end) {
            return 0;
        }
        
        int left = price[start] * year + solve(price, start + 1, end, year + 1);
        int right = price[end] * year + solve(price, start, end - 1, year + 1);
        
        return Math.max(left, right);
    }
    
    public static int findProfit(int price[], int n) {
        return Innoskrit.solve(price, 0, n - 1, 1);
    }
    
	public static void main (String[] args) {
		int price[] = new int[]{2, 3, 5, 1, 4};
		int n = 5;
		System.out.println(Innoskrit.findProfit(price, n));
	}
}




Output:

50

Time and Space Complexity

Time Complexity:

Space Complexity: