[AlgoSpot]デジタルゲーム

maxDiff(left, right) =           
MAX ( 
arr[left] - maxDiff(left+1, right),    //왼쪽 점수 가져가기
arr[right] - maxDiff(left, right-1),   //오른쪽 점수 가져가기
-maxDiff(left+2, right),               //왼쪽 2개 제거
-maxDiff(left, right-2)                //오른쪽 2개 제거
)

현재 플레이어를 A, 다음 플레이어를 B라고 할때 
maxDiff(left, right)상태에서 
arr[left] - maxDiff(left+1, right) 
= 가장 왼쪽 점수 - (B점수 - A점수의 최대값)
= 가장 왼쪽 점수 + A점수 - B점수 

import java.util.Scanner;

public class Main {
    public static int C, N;
    public static int [] arr = new int[51];
    public static int[][] cache = new int[51][51];
    public static int INF = 987654321;

    public static int maxDiff(int left, int right) {
        //기저 사례 : 수가 하나도 남지 않았을 때
        if (left > right) return 0;
        //다이나믹 프로그래밍
        if (cache[left][right] != -INF) return cache[left][right];
        int maxValue = -INF;
        //4가지 상황 고려
        //1. 왼쪽 수 하나 가져가기
        maxValue = Math.max(maxValue, arr[left] - maxDiff(left + 1, right));
        //2. 오른쪽 수 하나 가져가기
        maxValue = Math.max(maxValue, arr[right] - maxDiff(left, right - 1));
        if (right - left + 1 >= 2) {
            //3. 왼쪽 수 두개 제거
            maxValue = Math.max(maxValue, -maxDiff(left+2, right));
            //4. 오른쪽 수 두개 제거
            maxValue = Math.max(maxValue, -maxDiff(left, right-2));
        }
        cache[left][right] = maxValue;
        return cache[left][right];
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        C = sc.nextInt();
        for (int c = 0; c < C; c++) {
            N = sc.nextInt();
            //초기화
            for (int i = 0; i < N; i++) {
                arr[i] = sc.nextInt();
                for (int j = 0; j < N; j++)
                    cache[i][j] = -INF;
            }
            //메인 함수 실행
            System.out.println(maxDiff(0, N-1));
        }
    }
}