Game of Chefs Java Solution

import java.util.*;
class Main {
    public static void main(String[] args) {


        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        while(t-->0){
            int n = sc.nextInt();
        int a[] = new int[n + 1];
        for(int i = 1; i <= n; ++i)
            a[i] = sc.nextInt();
        long dp[][] = new long[n + 123][n + 123];
        for(int l = n; l >= 1; --l) {
            for(int r = l; r <= n; ++r) {
                if(r - l == 0) {
                    dp[r][l] = a[r];
                }else if(r - l == 1){
                    dp[l][r] = Math.max(a[l], a[r]);
                }else if(r - l == 2) {
                    // 1 2 3
                    dp[l][r] = Math.max(a[l] + Math.min(a[l + 1], a[l + 2]), a[r] + Math.min(a[r - 1], a[r - 2]));
                }else {
                    // 1 2 3 4
                    dp[l][r] = Math.max(a[l] + Math.min(dp[l + 2][r], dp[l + 1][r - 1]), a[r] + Math.min(dp[l][r - 2], dp[l + 1][r - 1]));
                }
            }
        }
        System.out.println(dp[1][n]);
        }
        sc.close();
    }
}