Example: Optimal Pick Strategy

You are given an array of moves and you have to figure out the best pick strategy to maximize your return when two players alternate picking.

x: 3, 9, 1, 2

Rationale: In array [i,j] player 1 either pick i or j. If P1 picks i, P2 is left with [i+1,j], if he picks j, P2 is left with [i,j-1]. We can then populate the table picking the max between:

• x[i] + d[i+1,j][1]
• x[j] + d[i,j-1][1]

Note that the second value will be the corresponding element d[i+1,j][0] or d[i, j-1][0] based on whether i or j gave the best solution to P1.

• First we populate the diagonal considering that there is only one element so if P1 picks the element, P2 is left with nothing. x: 3, 9, 1, 2

---	0	1	2	3
0	(3,0)
1		(9,0)
2			(1,0)
3				(2,0)

• We then proceed with sequences of increasing len starting from 2. x: 3, 9, 1, 2

---	0	1	2	3
0	(3,0)	(9,3)	(4,9)	(11,4)
1		(9,0)	(9,1)	(10,2)
2			(1,0)	(2,1)
3				(2,0)

bestStrategy(x)
    n = x.len
    let d[0..n-1, 0..n-1] and m[0..n-1, 0..n-1] be two tables
    for i = 0 to n-1
        d[i,i] = (x[i],0)

    for l = 2 to n
        for i = 0 to n-l-1
            j = i+l
            a = x[i] + d[i+1,j][1]
            b = x[j] + d[i, j-1][1]
            if(a>b)
                d[i,j] = (a, d[i+1,j][0])
                m[i,j] = i
            else
                d[i,j] = (b, d[i, j-1][0])
                m[i,j] = j
    print("Maximum score is: " + d[0,n-1]
    print("P1 moves:")

    # Retrieve the moves
    i, j = 0, n - 1
    moves = []
    while i <= j:
        if m[i,j] == i:
            moves.append(i)
            i += 1
        else:
            moves.append(j)
            j -= 1
    print(moves)
    return d[0][n - 1][0], moves