package com.jiucaiyuan.net.question;



/**

 * 拿纸牌，得到最大分数

 * 给定一个整形数组arr，代表数值不同的纸牌排成一条线。玩家A和玩家B依次拿走每张纸牌，

 * 规定玩家A先拿，玩家B后拿，但是每个玩家每次只能拿走最左或者最右侧的纸牌，玩家A和

 * 玩家B都是绝顶聪明。请返回最后胜利者的分数

 * <p>

 * Created by jiucaiyuan on 2022/3/2.

 */

public class CardsSelect {

    /**

     * 给一个纸牌，拿牌规则，从最左侧或者从最右侧拿牌，两个人轮流拿，能拿到最大积分数是多少

     *

     * @param arr

     * @return

     */

    public static int win(int[] arr) {

        if (arr == null || arr.length == 0) {

            return 0;

        }

        //

        return Math.max(firstSelect(arr, 0, arr.length - 1), secondSelect(arr, 0, arr.length - 1));

    }



    /**

     * @param arr 纸牌

     * @param l   可选择最左侧纸牌

     * @param r   可选择最右侧纸牌

     * @return 拿走一张牌得到的最大分数

     */

    public static int firstSelect(int[] arr, int l, int r) {

        if (l == r) {

            return arr[l];

        }

        //先拿要得到最大分数

        return Math.max(arr[l] + secondSelect(arr, l + 1, r), arr[r] + secondSelect(arr, l, r - 1));

    }



    /**

     * @param arr 纸牌

     * @param l   先手拿之前可选择最左侧纸牌

     * @param r   先手拿之前可选择最右侧纸牌

     * @return

     */

    private static int secondSelect(int[] arr, int l, int r) {

        if (l == r) {

            return 0;

        }

        //先手会让我得到最少的分数

        return Math.min(firstSelect(arr, l + 1, r), firstSelect(arr, l, r - 1));

    }



    /**

     * 从递归中改进过来，动态规划版本

     * 

     * @param arr

     * @return

     */

    public static int dp(int[] arr) {

        if (arr == null || arr.length == 0) {

            return 0;

        }

        int[][] f = new int[arr.length][arr.length];

        int[][] s = new int[arr.length][arr.length];

        //对角线位置值可以根据数组中值固定得到，初始化到表中

        for (int i = 0; i < arr.length; i++) {

            f[i][i] = arr[i];

        }

        int row = 0;

        int col = 1;

        //对角线开始位置，row行 col列

        while (col < arr.length) {

            int i = row;

            int j = col;

            while (i < arr.length && j < arr.length) {

                f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);

                s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);

                i++;

                j++;

            }

            col++;

        }

        return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);



    }





    public static void main(String[] args) {

//        int[] arr = {1, 4, 100, 100, 8};

        int[] arr = {1, 8};

        System.out.println(win(arr) + "<------->" + dp(arr));

    }



}