Recursive Brute-Force I have to recursively solve the following problem, using a brute force approach:

Suppose two people, A and B, have an even number of ordered boxes, each with a given value. For example, boxes = {5, 3, 7, 10}. They need to split the boxes between them, in this way: person A chooses either the first or the last box in the set, then person B does the same, and so on until there are no boxes left. 

Person A wants to know, what's the maximum value he can get, in total, bearing in mind that at each turn person B can make two choices as well. In other words, the problem is to come up with an algorithm that simulates all the choices of both people, considering they're all aiming to have the maximum value in the long term.

So, for now I have this:

public static int maxValue(ArrayList &lt;Integer&gt; boxes, int choice, int person){
    int value;

    //Stop condition - if there are no more boxes, return 0
    if (boxes.isEmpty())
        return 0;

    if (choice == 0) //Person chose the first box in the sequence
        value = boxes.remove(0);
    else //Person chose the last box in the sequence
        value = boxes.remove(boxes.size() - 1);

    //Person A makes a choice, checking which one works best in the long run
    if (person == 1)
        return (value + max(maxValue(boxes, 0, 2), maxValue(boxes, 1, 2)));

    //Person B makes a choice, checking which one works best in the long run
    else
        return (value + max(maxValue(boxes, 0, 1), maxValue(boxes, 1, 1)));
}


For an input of boxes = {5, 3, 7, 10}, the code is supposed to produce 15, yet the one I wrote above gives me 25. After placing some debugging prints, I saw it goes:


Person A chooses '10'
Person B chooses '7'
Person A chooses '3'
Person B chooses '5'


And then just adds all the values. I'm figuring it's because of the way the function is called by person A with reference to person B (in max(maxValue(boxes, 0, 2), maxValue(boxes, 1, 2))), and vice-versa, and also because of that stop condition (if I change it slightly the value returned is different).
if it really has to be brute force solution, then you have to check all possible combinations of take first/take last item for both players

you know that there are 4 items, so every player takes two of them, combinations are (for each player):

take first (0), take first (0)
take first (0), take last  (1)
take last  (1), take first (0)
take last  (1), take last  (1)


as you can see, numbers are similar to binary numbers equal to 0-3(dec)

second player should do the same in an inner loop for every iteration of first player (outer loop)

pseudo code would be:

ArrayList &lt;Integer&gt; boxes = {5, 3, 7, 10}

boolean shouldTakeFirst(int combination, int iteration) {
    return (combination &amp; (1&lt;&lt;iteration)) &gt; 0; // checks if i-th bit of combination is "1"
}

int player1Score(int combinationP1, int combination P2) {
    int score = 0;
    for (int i=0; i&lt;boxes.size()/2; i++) {
        score += shouldTakeFirst(combinationP1, i) ? boxes.popFirst() : boxes.popLast(); // assuming that .popFirst() and .popLast() remove elements after taking them
        shouldTakeFirst(combinationP2, i) ? boxes.first() : boxes.last();
    }
    return score;
}

for (int i=0; i &lt; Math.pow(2, boxes.size()/2); i++) {
    for (int j=0; j &lt; Math.pow(2, boxes.size()/2); j++) {
        int p1Score = player1Score(i, j);
        int p2Score = sum(boxes) - p1Score;

        // check if scores better than max and remember/print it
    }
}