Optimal Game Strategy-I

#1

one test case is wrong but rest of test cases are right

import java.util.*;

public class Main {

public static void main(String args[]) {
    // Your Code Here
	Scanner scn = new Scanner(System.in);
	int n = scn.nextInt();
	int [] arr = new int [n];
	for (int i=0;i<arr.length;i++){
		arr[i] = scn.nextInt();
	}
	int sume=0,sumo=0;
	for(int j=0;j<n;j++){
		if(j%2==0)
		  sume=sume+arr[j];
		else
		 sumo=sumo+arr[j];

	}
	if(sume>sumo)
	  System.out.println(sume);
	 else
	 System.out.println(sumo); 
}

}

#2

Hey @uttkarsh17goswami
what are you doing ??
its Dp problem
try for this input
4
5 3 7 10
correct output : 15

#3

So what should be the right approach to solve this ques

#4

@uttkarsh17goswami
At first look , this looks like a Greedy problem but it is clearly not so. This can clearly be observed in a simple testcase like
4
5 4 8 6
Clearly , we would need an optimal solution for this. At each instance we would need to consider two possibilities that we can pick the first as well as the last element of the remaining array. Both these possibilities give rise to two more possibilities depending on the other player. Since the second player plays optimally and try to minimise our score. So overall we have two possibilities at each instance.
For the first possibility , where we could pick the first element , the other player will pick the next element from the side that would minimise our total score.
Similarly , for the second possibility , where we can pick the last element , the other player would still pick the next element from the side that would minimise our total score.
We entertain both these cases and take the maximum result of the two and return that result.
We take two pointer variables , say ā€˜iā€™ and ā€˜jā€™ which each represent the starting and the ending point of the remaining array currently in consideration. We work till the two pointers cross each other.

// Consider both the possibilities. You can pick either the first or the last coin.
    // Since the opponent plays optimally , we would get the minimum of the remaining coins for each choice.
    ll pickFirst = coins[i] + min( optimalGame(i+2,j) , optimalGame(i+1,j-1) ) ;
    ll pickLast = coins[j] + min( optimalGame(i,j-2) , optimalGame(i+1,j-1) ) ;

    // Pick the max of two as your final result
    ll ans = max(pickFirst,pickLast);