# subject

## describe

Given an integer array arr, which represents cards of different values, a line is formed. Player A and Player B take each card in turn, requiring Player A to take it first and Player B to take it later, but each player can only take the left or right card at a time. Player A and Player B are brilliant. Return to the winner's score.

[Example]

arr=[1,2,100,4].

Player A can only take 1 or 4 at the beginning. If Player A takes 1 at the beginning, the alignment changes to [2,100,4]. Player B can take 2 or 4 then continue to take Player A's turn.

If Player A takes away 4 at the beginning, the alignment changes to [1,2,100], then Player B can take away 1 or 100, and then continue to take Player A's turn...

Player A, as the ultimate smart person, won't take 4 first because Player B will take 100 after taking 4. So Player A will take 1 first and change the alignment to [2,100,4]. Player B will take 100 away by Player A whatever he chooses. Player A will win with a score of 101. So go back to 101.

arr=[1,100,2].

Player A starts with 100 as the smartest person, taking either 1 or 2. Player B wins with a score of 100. So return to 100.

# Solving problems

(1) Recursion problems For ease of understanding, you can list the entire process of recursion

(2) Set the input arr to [1, 8, 10, 6]

(3) using the win function to find the optimal solution of arr, that is, to get the optimal solution first in hand and then in hand

(4) where 0 and 3 represent a double pointer to the front and back values of the array

>>>win([1, 8, 10, 6], 4) max(f([1, 8, 10, 6], 0, 3), s([1, 8, 10, 6], 0, 3))

(5) For the first-hand f-function, it resolves to take the left or the right so that it has the largest result and can be converted to,

>>>f([1, 8, 10, 6], 0, 3) max(1 + s([1, 8, 10, 6], 1, 3), 6 + s([1, 8, 10, 6], 0, 2))

(6) For the second-hand s-function, it resolves to take the left or the right, so that the result of the opponent is the smallest and can be converted to

>>>s([1, 8, 10, 6], 0, 3) min(f([1, 8, 10, 6], 1, 3), f([1, 8, 10, 6], 0, 2))

(7) Similarly, 1,3 means taking the card on the left, 0,2 means taking the card on the right.

>>>1 + s([1, 8, 10, 6], 1, 3) 1 + min(f([1, 8, 10, 6], 2, 3), f([1, 8, 10, 6], 1, 2)) >>>6 + s([1, 8, 10, 6], 0, 2) 6 + min(f([1, 8, 10, 6], 1, 2), f([1, 8, 10, 6], 0, 1)) >>>f([1, 8, 10, 6], 1, 3) max(8 + s([1, 8, 10, 6], 2, 3), 6 + s([1, 8, 10, 6], 1, 2)) >>>f([1, 8, 10, 6], 0, 2) max(1 + s([1, 8, 10, 6], 1, 2), 10 + s([1, 8, 10, 6], 0, 1))

(8) List further below

>>>f([1, 8, 10, 6], 2, 3) max(10 + s([1, 8, 10, 6], 3, 3), 6 + s([1, 8, 10, 6], 2, 2)) max(10, 6) 10 >>>f([1, 8, 10, 6], 1, 2) max(8 + s([1, 8, 10, 6], 2, 2), 10 + s([1, 8, 10, 6], 1, 1)) max(8, 10) 10 >>>f([1, 8, 10, 6], 1, 2) max(8 + s([1, 8, 10, 6], 2, 2), 10 + s([1, 8, 10, 6], 1, 1)) max(8, 10) 10 >>>f([1, 8, 10, 6], 0, 1) max(1 + s([1, 8, 10, 6], 0, 0), 8 + s([1, 8, 10, 6], 1, 1)) max(1, 8) 8 >>>s([1, 8, 10, 6], 2, 3) min(f([1, 8, 10, 6], 3, 3), f([1, 8, 10, 6], 2, 2)) min(6, 10) 6 >>>s([1, 8, 10, 6], 1, 2) min(f([1, 8, 10, 6], 2, 2), f([1, 8, 10, 6], 1, 1)) min(10, 8) 8 >>>s([1, 8, 10, 6], 1, 2) min(f([1, 8, 10, 6], 2, 2), f([1, 8, 10, 6], 1, 1)) min(10, 8) 8 >>>s([1, 8, 10, 6], 0, 1) min(f([1, 8, 10, 6], 1, 1), f([1, 8, 10, 6], 0, 0)) min(8, 1) 1

(9) Return to calculation result (7)

>>> 1 + s([1, 8, 10, 6], 1, 3) 1 + min(f([1, 8, 10, 6], 2, 3), f([1, 8, 10, 6], 1, 2)) 1 + min(10, 10) 11 >>> 6 + s([1, 8, 10, 6], 0, 2) 6 + min(f([1, 8, 10, 6], 1, 2), f([1, 8, 10, 6], 0, 1)) 6 + min(10, 8) 14 >>> f([1, 8, 10, 6], 1, 3) max(8 + s([1, 8, 10, 6], 2, 3), 6 + s([1, 8, 10, 6], 1, 2)) max(14, 14) 14 >>> f([1, 8, 10, 6], 0, 2) max(1 + s([1, 8, 10, 6], 1, 2), 10 + s([1, 8, 10, 6], 0, 1)) max(9, 11) 11

(10) Back to step (5)

>>>f([1, 8, 10, 6], 0, 3) max(1 + s([1, 8, 10, 6], 1, 3), 6 + s([1, 8, 10, 6], 0, 2)) max(11, 14) 14

(11) Return to step (6)

>>>s([1, 8, 10, 6], 0, 3) min(f([1, 8, 10, 6], 1, 3), f([1, 8, 10, 6], 0, 2)) min(14, 11) 11

(12) Therefore, the optimal score scheme is to hold the card first, take 6 then 8, with a score of 14, and take only 10 and 1 for the later scheme, with a score of 11.

# Code

def win(arr, sz): if sz == 0: return 0 else: return max(f(arr, 0, sz - 1), s(arr, 0, sz - 1)) #First hand def f(arr, i, j): if i == j: return arr[i] else: return max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1)) #Backhand def s(arr, i, j): if i==j:#Indicates that you have taken it first and there is only one situation left return 0 else: return min(f(arr, i + 1, j), f(arr, i, j - 1))#First you want to win, then you need to take the worst if __name__=="__main__": arr = [1, 8, 10, 6] print(win(arr, len(arr)))