Optimal game strategy - i tried doing it without recursion

#1

import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner scn = new Scanner(System.in);
int n = scn.nextInt();
int[] arr = new int[n];
for(int i=0 ; i < n ; i++){
arr[i] = scn.nextInt();

	}
	System.out.println(game(arr));
}

	public static int game(int[] arr){

		int s1=0;
		int s2=0;
		for(int i = 0 ;i < arr.length ; i= i+2){
			s1 = s1 + arr[i];
		}
		for(int j=1 ; j < arr.length ; j=j+2){
			s2 = s2 + arr[j];
		}

		if( s1 > s2){
			return s1;
		}else{
			return s2;
		}


	}
}
#2

@asthaaggarwal2,

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 minimize 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.

2 choices are:

  1. The user chooses the ith coin with value Vi: The opponent either chooses (i+1)th coin or jth coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) )

  2. The user chooses the jth coin with value Vj: The opponent either chooses ith coin or (j-1)th coin. The opponent intends to choose the coin which leaves the user with minimum value.
    i.e. The user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) )

If you have to avoid using recursion you need a dynamic programming approach and make a 2D array and then implement your approach. You are missing out on a test case in this approach.

#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.