Hi, could someone please explain how to solve this problem ?
Thanks in Advance !!
Let A_i denote the value of the ith number. Let dp_{i,j} denote the difference between the score of the first player and the second player S_{p1} - S_{p2} if they play the game between the indices i and j. Notice that
dp_{i,j} = max(A_j - dp_{i,j-1}, A_i - dp_{i+1,j}). You can choose A_i or A_j, and the negative sign is because player one becomes player two.
4 Likes
Hey there @everule1 , can you please explain it a little bit more? It will be a great help!!
Thanks!
For every interval (i, j) there is a fixed person who is going to be playing on that interval. dp[i][j] stores the difference between the scores of the person who is playing on that interval and then person who plays next if they are only allowed to use that interval. Since the person playing can only take the ends of the intervals, only i and j are available.
Call the person taking currently A. If he takes i, then the interval becomes (i + 1, j). dp[i + 1][j] stores the value of B - A, so you subtract it from a[i] to get A + a[i] - B which is the value for the current segment if A takes i. It is very similar for if A takes j, and you compare them to get dp[i][j].
dp[i][j] = max(a[i] - dp[i + 1][j], a[j] - dp[i][j - 1])