CareerCup

this is the case for 2 players:
Take 5 first ..
.. then list is ( 12, 24, 10)
they take 12 or 10 either list look like (24, 10) or (12, 24)

Now pick 24 ..,

you sum is 29 and oppenent sum is 22.

..but i didnt understand ..what this to do with software engineer question.. i really wonder.,

Dynamic Programming may be one solution. I googled and found it. If you do not understand the below solution, please google it.

S[i,j] be an array of coins and that is coins from 0..........i-1 and j+1 ........n have already been picked up. We have coins i through j remaining coins to pick. And it now our chance to pick.

Representation of S: S[ .......,i,......j,......]

If it is our move, we have cleverly pick such that the neighbor sum is minimized.

Case A: when we have picked 'i' from the available coins i through j. Then Neighbor has a chance to pick coin at (i+1)th or jth location. His resultant value would be either S[i+2, j] or S[i+1, j-1]. We have to minimize this result.

A = Min {S[i+2, j], S[i+1, j-1]} + coin value. This would be minimizing opponent's sum.

Case B: Similar, when we have picked 'j' . After that there would be coins i through j-1 are left. He can pick either coin @ i or j-1 location

B = Min {S[i+1, j-1], S[i, j-2]} + value of coin.
This would be minimizing opponent's sum.

Finally, we have Maximize all the moves starting from 0...n

Maximize{ A, B }

Complexity O(n^2).

#include<stdio.h>
#include<conio.h>
int main()
{
int a[5]={12,24,10,25,8};
int s=0;
int e=4;
int max=a[s]+a[e];
while(s < e)
{
if((a[s]+a[e])> max)
{
max=a[s]+a[e];
}
if(a[s]>a[e])
{
--e;
}
else
++s;
}
printf("%d",max);
getchar();
getchar();
return 0;
}

My java implementation:

private static Pair<Integer, Integer> getMaxPossibleWithSmartOpponent(int[] nos, boolean isMainPlayer, int p1, int p2) {
        if(nos.length == 1) {
            if(isMainPlayer) return Pair.of(p1 + nos[0], p2);
            else return Pair.of(p1, p2 + nos[0]);
        }
        // call for opponent assuming left is picked
        Pair<Integer, Integer> leftAns = null;
        if(isMainPlayer) {
            leftAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 1, nos.length), 
                !isMainPlayer, p1 + nos[0], p2);
        } else {
            leftAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 1, nos.length), 
                    !isMainPlayer, p1, p2 + nos[0]);
        }
        
        // call for opponent assuming right is picked
        Pair<Integer, Integer> rightAns = null;
        if(isMainPlayer) {
            rightAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 0, nos.length-1), 
                !isMainPlayer, p1 + nos[nos.length-1], p2);
        } else {
            rightAns = getMaxPossibleWithSmartOpponent(Arrays.copyOfRange(nos, 0, nos.length-1), 
                    !isMainPlayer, p1, p2 + nos[nos.length-1]);
        }
        
        if(isMainPlayer) {
            return leftAns.getLeft() > rightAns.getLeft() ? leftAns : rightAns;
        } else {
            return leftAns.getRight() > rightAns.getRight() ? leftAns : rightAns;
        }
    }

I found below links useful:
geeksforgeeks.org/dynamic-programming-set-31-optimal-strategy-for-a-game/
leetcode.com/2011/02/coins-in-line.html

tech-queries.blogspot.com/2011/06/get-maximum-sum-from-coins-in-line.html