【左神算法】有一排正数，玩家A和玩家B都可以看到。 每位玩家在拿走数字的时候，都只能从最左和最右的数中选择一个。 玩家A先拿，玩家B再拿，两人交替拿走所有的数字， 两人都力争自己拿到的数的总和比对方多

1.问题

有一排正数，玩家A和玩家B都可以看到。
每位玩家在拿走数字的时候，都只能从最左和最右的数中选择一个。
玩家A先拿，玩家B再拿，两人交替拿走所有的数字，
两人都力争自己拿到的数的总和比对方多。请返回最后获胜者的分数。
例如：
5,2,3,4
玩家A先拿，当前他只能拿走5或者4。
如果玩家A拿走5，那么剩下2，3，4。轮到玩家B，此时玩家B可以选择2或4中的一个，…
如果玩家A拿走4，那么剩下5，2，3。轮到玩家B，此时玩家B可以选择5或3中的一个，…

2.思路&code

2.1 win1()思路

win1()：由于存在AB玩家都可以看到数字的大小，所以每次都在做一个决策。先开始的玩家势必会拿最大数，而第二玩家势必只能在第一个玩家拿到最大的前提下，自己去拿剩下数字中的最大者。所以用递归就可以很清晰的表达。
1.针对谁先拿必然是先拿最大者，而后者就是拿最次大者。依序就是 first->second->first—>second …
a.其中 当i == j 对于first来说 可以拿到arr[i]
b.i == j 对于second来说 拿不到arr[i] 因为first具有优先权。

	//1.针对谁先拿必然是先拿最大者，而后者就是拿最小者。依序就是 first->second->first—>second .....
    // a.其中 当i == j 对于first来说 可以拿到arr[i]
    // b.i == j 对于second来说 拿不到arr[i] 因为first具有优先权。
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
    }

    public static int first(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        return Math.max(arr[i] + second(arr, i + 1, j), arr[j] + second(arr, i, j - 1));
    }

    public static int second(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        return Math.min(arr[i] + first(arr, i + 1, j), arr[j] + first(arr, i, j - 1));
    }

2.2 win2思路

win2()思路
win1中递归会存在大量的重复计算。因此我们可以改成dp。dp主要是基于已知的条件来对下一项进行选择。而first玩家的决策，会影响到second玩家，因此。需要二维dp来解决这个问题。first[][] 记录first玩家的决策路径，second[][]记录second玩家的决策路径。i记录行号，j记录列。i的值不可能大于j 所以左下三角是没有数据的。

	public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //初始化状态  dp方程
        int[][] first = new int[arr.length][arr.length];
        int[][] second = new int[arr.length][arr.length];

        for (int j = 0; j < arr.length; j++) {
            //初始化参数
            first[j][j] = arr[j];
            for (int i = j-1; i >=0 ; i--) {
                //进行决策
                first[i][j] = Math.max(arr[i]+second[i+1][j],arr[j]+second[i][j-1]);
                second[i][j] = Math.max(first[i+1][j],first[i][j-1]);
            }
        }
        return Math.max(first[0][arr.length-1],first[0][arr.length-1]);
    }

2.3 win3思路

win3的思路是借鉴win1 是基于win1来说的，win1中需要计算first和second的两个值。如果这样想 只计算一个值value，总数sum-value 只需要比较两者最大值就可以了。

 	public static int win3(int [] arr){
        if (arr == null || arr.length == 0){
            return  0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length ; i++) {
            sum += arr[i];
        }
        int socore = p(arr,0,arr.length-1);
        return Math.max(sum-socore,socore);
    }

    public static int p(int [] arr,int i,int j){
        if (i == j){
            return arr[i];
        }
        if (i + 1 == j){
            return Math.max(arr[i],arr[j]);
        }
        return Math.max(arr[i]+Math.min(p(arr,i+2,j),p(arr,i+1,j-1)),
                arr[j]+Math.min(p(arr,i+1,j-1),p(arr,i,-2)));
    }

2.4 code

	package com.ncst.offer.ch1;

	import java.util.ArrayList;

	/**
	 * @author i
	 * @create 2020/7/1 10:20
	 * @Description
	 */
	public class Problem_03_CardsInLine {

    //1.针对谁先拿必然是先拿最大者，而后者就是拿最小者。依序就是 first->second->first—>second .....
    // a.其中 当i == j 对于first来说 可以拿到arr[i]
    // b.i == j 对于second来说 拿不到arr[i] 因为first具有优先权。
    public static int win1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(first(arr, 0, arr.length - 1), second(arr, 0, arr.length - 1));
    }

    public static int first(int[] arr, int i, int j) {
        if (i == j) {
            return arr[i];
        }
        return Math.max(arr[i] + second(arr, i + 1, j), arr[j] + second(arr, i, j - 1));
    }

    public static int second(int[] arr, int i, int j) {
        if (i == j) {
            return 0;
        }
        return Math.min(arr[i] + first(arr, i + 1, j), arr[j] + first(arr, i, j - 1));
    }

    public static int win2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        //初始化状态  dp方程
        int[][] first = new int[arr.length][arr.length];
        int[][] second = new int[arr.length][arr.length];

        for (int j = 0; j < arr.length; j++) {
            //初始化参数
            first[j][j] = arr[j];
            for (int i = j-1; i >=0 ; i--) {
                //进行决策
                first[i][j] = Math.max(arr[i]+second[i+1][j],arr[j]+second[i][j-1]);
                second[i][j] = Math.max(first[i+1][j],first[i][j-1]);
            }
        }
        return Math.max(first[0][arr.length-1],first[0][arr.length-1]);
    }


    public static int win3(int [] arr){
        if (arr == null || arr.length == 0){
            return  0;
        }
        int sum = 0;
        for (int i = 0; i < arr.length ; i++) {
            sum += arr[i];
        }
        int socore = p(arr,0,arr.length-1);
        return Math.max(sum-socore,socore);
    }

    public static int p(int [] arr,int i,int j){
        if (i == j){
            return arr[i];
        }
        if (i + 1 == j){
            return Math.max(arr[i],arr[j]);
        }
        return Math.max(arr[i]+Math.min(p(arr,i+2,j),p(arr,i+1,j-1)),
                arr[j]+Math.min(p(arr,i+1,j-1),p(arr,i,-2)));
    }


    public static int[] gengerateRandomArray() {
        int[] res = new int[(int) Math.random() * 20 + 1];
        for (int i = 0; i < res.length; i++) {
            res[i] = (int) Math.random() * 20 + 1;
        }
        return res;
    }

    public static void main(String[] args) {
        int timeNum = 500;
        boolean flag = false;
        for (int i = 0; i < timeNum; i++) {
            int[] res = gengerateRandomArray();
            int res1 = win1(res);
            int res2 = win2(res);
            int res3 = win3(res);
            if (res1 != res2 && res2 == res3) {
                flag = true;
            }
        }

        if (flag) {
            System.out.println("233333333333");
        } else {
            System.out.println("666666666666");
        }
    }

}