• Source 
    1. import java.util.Arrays;
    2. import java.util.Scanner;
    3.  
    4. class Main {
    5.     static int[] treats;       
    6.     static int[][] dp;
    7.     static int n;
    8.  
    9.     public static void main(String[] args) throws java.lang.Exception {
    10.         Scanner sc = new Scanner(System.in);
    11.         n = sc.nextInt();
    12.         treats = new int[n];
    13.         for (int i = 0; i < n; i++) {
    14.             treats[i] = sc.nextInt();
    15.         }
    16.         dp = new int[n][n];
    17.         for (int i = 0; i < n; i++) {
    18.             Arrays.fill(dp[i], -1);
    19.         }
    20.  
    21.         System.out.println(profit(0, n - 1));
    22.  
    23.     }
    24.  
    25.     private static int profit(int be, int en) {
    26.         if (be > en) {
    27.             return 0;
    28.         }
    29.         if (dp[be][en] != -1) {
    30.             return dp[be][en];
    31.         }
    32.         int year = n - (en - be + 1) + 1;
    33.         return dp[be][en] = Math.max(profit(be + 1, en) + treats[be] * year, profit(be, en - 1) + treats[en] * year);
    34.     }
    35. }