ANSWER ALL THE QUESTIONS AND WRITE A JAVA CODE START AT INDEX 1

its an algorithm question

Let nN be an even number. Consider a row of n coins represented as an array A=[v1,,vn], where vi is the value of the i th coin. Two players alternate turns, with Player 1 starting. At each turn, a player chooses either the first or the last coin in the row, and takes it. Your goal is to design an algorithm that determines the maximum possible gain Player 1 can definitely win. Assume Player 2 is extremely smart and plays to maximize their payoff. We will use dynamic programming to solve this problem. Define the subproblems MaxGain (i,j) to be the maximum guaranteed payoff for Player 1 if given the subarray [vi,,vj] of even length (i.e., ji+1 must be a positive even number). 1. Suppose the row of coins is A=[1,1,1,2,2,2] What payoff can Player 1 definitely win regardless of the opponent's moves? Describe in words the optimal strategy for this particular instance. 2. Fill out the following table for the A defined in the previous part. If entry MaxGain [i,j]=X, then it means that the value is not defined since ji+1 is not a positive even number. 3. Base Cases: State the base cases for MaxGars (i,j) and their values. (Hint: Consider subarrays of length 2.) 4. Recurrence: Give and justify the recurrence MaxGass satisfies. 5. Algorithm: Describe an algorithm that computes MaxGaIn and outputs the maximum possible gain of Player 1, regardless of Player 2 's moves. Your algorithm should describe in simple words how the MaxGann array is filled. Use pseudocode only if necessary. State and justify the run time of your algorithm as a expression. Table 1: Fill in the entries for MaxGans (i,j)