Question

link

两个人（A，B）参与一个游戏，规则如下：

1）一个随机的整数数列有偶数个数,a1,a2,…a2n

2）A 先从数列取数，但只能从两头取,a1 or a2n

3)然后Ｂ取数，也是只能从剩下的两头取，依此类推，两个人轮流，都只能从两头取

Output the max sum of numbers that player 1 is going to get.

Solution

This question can be solved with DP by using the following 3 equations:

1. sum[i][j] sum of number from i to j
2. val[i][j]: the max value that can be obtained if only the range [i,j] is left and you take the move first
3. pos[][] is related to val[][], as it denotes whether we take i or j

After we got sum[][] array fully filled up, the transition equation of val[][] looks like:

val[x][y] = sum[x][y] - MIN( val[x+1][y], val[x][y-1] )

As for pos[][]:

pos[x][y] = x  if val[x+1][y] < val[x][y-1]
            y  otherwise

Code

public int getMaxSumPlayerOne(int[] input) {
    int len = input.length;
    // sum[i][j] sum of number from i to j
    int[][] sum = new int[len][len];
    // val[i][j]: the max value that can be obtained if only
    // the range [i,j] is left and you take the move first
    int[][] val = new int[len][len];
    // pos is related to val, as it denotes whether we take i or j
    int[][] pos = new int[len][len];

    // 1. fill in sum[][]
    for (int x = 0; x < len; x++) {
        for (int y = x; y < len; y++) {
            if (x == y) {
                sum[x][y] = input[x];
            } else if (x == 0) {
                // fill up the first row in the sum[][] dp array
                sum[x][y] = sum[x][y - 1] + input[y];
            } else {
                // starting from the 2nd row, it's gonna make use of 1st row
                // x >= 1
                sum[x][y] = sum[0][y] - sum[0][x - 1];
            }
        }
    }

    // 2. fill in val[][] and pos[][]
    for (int x = len - 1; x >= 0; x--) {
        for (int y = x; y < len; y++) {
            if (x == y) {
                val[x][y] = input[x];
                pos[x][y] = x;
            } else {
                // when I choose either x or y, I look at what the opponent
                // is gonna get after my move, then chose the smaller
                // v[][] for the remaining part
                val[x][y] = sum[x][y] - Math.min(val[x + 1][y], val[x][y - 1]);
                pos[x][y] = val[x + 1][y] < val[x][y - 1] ? x : y;
            }
        }
    }
    this.printSteps(pos, len);
    return val[0][len - 1];
}

Testing

Input {1, 4, 3, 2}
Player 1 take position 3
Player 2 take position 2
Player 1 take position 1
Player 2 take position 0
max sum for player 1 is 6

Input {7, 5, 2, 6, 9, 8, 3, 4}
Player 1 take position 0
Player 2 take position 1
Player 1 take position 7
Player 2 take position 6
Player 1 take position 5
Player 2 take position 4
Player 1 take position 3
Player 2 take position 2
max sum for player 1 is 25