• To solve this problem we will use the gap strategy.
• So first of all prepare a 2D array dp of size n*n (input array's length).
• Any cell, dp[i][j] will store the maximum value, which you can score while playing the game for subarray which starts from ith index and ends on jth index.
• At gap = 0, diagonal represents the cell which corresponds to only one element in the array as i equals j.
• Let's say that there is only one element in the input array. And as you get the first chance to pick, so you can pick the only present value and win the game.
• So at gap 0, the diagonal will store the same value to which the particular cell corresponds. For example consider the array: {20, 30, 2, 10}.

• At gap = 1, suppose there were two values in the input array then it means that you have two options to make a choice. So it's obvious that you will go with the greater value. And therefore the opponent will be left with the only option to pick i.e. smaller value. And this way you can ensure your win.

• To solve this problem further, we need an ideology. And the ideology says that, "When you do things, do your best and when things happen to you, assume the worst."
• As initially, you get to choose first i.e. you can either choose the starting value say i or the ending value say j. Then we will explore both the options, instead of going with the maximum among these two (which is the greedy approach) because there is a possibility that choosing a smaller value in the initial stage leads to a greater score later on.
• But when the opponent gets the chance to choose a value than we assume that he will choose such a value that the option left for you is the worst (minimum).

• At gap = 2, we have a subarray of 3 elements. Here at first we have two options to choose from. Like at dp[0][2], the subarray is {20, 30, 2}. And we can either choose 20 or 2. Suppose we choose 20 then the opponent can either choose 30 or 2. He will choose a value so that the value left behind contributes the minimum to your score i.e. 2, which makes him choose 30. Now we have only one option to choose i.e. 2 which makes your final score 22.
• And if we decide to choose 2 then the opponent can either choose 30 or 20. He will choose a value so that value left behind contributes the minimum to your score i.e. 20, which makes him choose 30. Now we have only one option to choose i.e. 20 which makes your final score 22.
• Either way your result is 22. So at dp[0][2], 22 will be stored.

• Similarly we will fill the dp[1][3];the subarray is {30, 2, 10}. And we can either choose 30 or 10. Suppose we choose 30 then the opponent can either choose 2 or 10. He will choose a value so that the value left behind contributes the minimum to your score i.e. 2, which makes him choose 10. Now you have only one option to choose i.e. 2 which makes your final score 32.
• And if we decide to choose 10 then the opponent can either choose 30 or 2. He will choose a value so that the value left behind contributes the minimum to your score i.e. 2, which makes him choose 30. Now we have only one option to choose i.e. 2 which makes your final score 12.
• Choosing 30 initially is a better option. So at dp[0][2], 32 will be stored.

• Moving to gap = 3, there is only one cell, dp[0][3], which will store the final answer as well.
• Let's try to fill this using formulas. Here at first you have two options i.e. either choosing 20 or 10. So if you decide to choose 20, then the opponent will have two options to choose i.e. 30 and 10. He will choose the one which will leave you with a minimum value. So basically we will have to choose the minimum of dp[1][2] (dp[i+1][j-1]) and dp[2][3] (dp[i+2][j]) which is 10.
And if you decide to choose 10, then the opponent will have two options to choose i.e. 20 and 2. He will choose the one which will leave you with a minimum value. So basically we will have to choose the minimum of dp[1][2] (dp[i+1][j-1]) and dp[0][1] (dp[i][j-2]) which is 30.

• And among these two minimums we will choose the one which will give maximum value after adding your choice. Like adding 10 to 20 (which was your first choice) gives 30. And adding 30 to 10 (which was your second choice) gives 40. Therefore we will store 40 at dp[0][3].
• To conclude this, we need to get the minimum of both the options when the opponent's options are explored and to decide your answer you need to add your choice to the corresponding minimums and choose the maximum among both.

For more clarity of this part; watch part of the video.

Let's try to code this!

//1 - To start with, define a 2D array of size (arr.length()) * (arr.length()).
//2 - Now apply a for rule to fill the dp diagonally initializing gap to 0 till gap remains less than arr.length().
//3 - Then define two variables i to 0 and j to gap.
//4 - After that apply a while loop to fill the (gap)th diagonal.
//5 - Then define a variable x. And check if (i+2) is less than or equal to j, if yes than put dp[i+2][j] in x otherwise put 0.
//6 - Similarly define a variable y. And check if (i+1) is less than or equal to (j-1), if yes then put dp[i+1][j-1] in y otherwise put 0.
//7 - Now similarly define a variable z. And check if (i) is less than or equal to (j-2), if yes then put dp[i][j-2] in z otherwise put 0.
//8 - Then add the min of x and y to arr[i] and add min of y and z to arr[j]. And then set the dp[i][j] with the maximum of these two values.
//9 - Increment i and j by 1 to make the while loop run for
//10 - After filling the dp completely, print dp[0][dp[0].length-1] where the final answer will be stored.

For more clarity of this part, watch part of the video. You may find the code in the video a bit different because the cases for gap at 0 and 1 are managed differently and a for loop has been used unlike the while loop used here. However, both the codes serve similar functionality.

We hope that this article was helpful. If somehow you are finding it difficult to understand this problem then we advise you to watch our video lecture of this problem.
Trust me it will just get easier to understand after you have watched the solution video.
You can contact us via our website. Doubts, suggestions and feedback are always welcomed.
It is also advised that you follow the sequence of modules and questions which is there on our website.
Keep practicing more and more problems daily. Meditate enough on each step of each problem.

All the best for an exciting future!
Happy Coding!