Coins in a Line

We have an array of integers which has numbers in it.each integer represents a currency note.You and your friend playing a game in which each can either take number(money) from left or right.That is each step you have two options either you take left most currency note or right most currency note.Now you need to maximize your money.

ex : array = {5,9,2,3}

Maximum amount we can make is {3,9} 9+3 = 12.

Java code for calculating maximum mount we can get in this play is :

public class MaxSumOfCoins {

 public static void main(String[] args) {
  int[] a = { 3, 2, 2, 3, 1, 2 };
  int maxSum = getMaxSum(a, 0, a.length - 1);
  System.out.println("Maximum sum we can obtain in this play is : "
    + maxSum);
 }

 private static int getMaxSum(int[] a, int i, int j) {

  if (j < 0 || i > a.length - 1 || i > j)
   return 0;

  // P1 = Ai + min { P(i+2, j), P(i+1, j-1) }
  int selectIandIplus1 = getMaxSum(a, i + 2, j);
  int selectIandJ = getMaxSum(a, i + 1, j - 1);
  int p1 = a[i]
    + (selectIandIplus1 < selectIandJ ? selectIandIplus1
      : selectIandJ);

  // P2 = Aj + min { P(i+1, j-1), P(i, j-2) }
  int selectJandIplus1 = getMaxSum(a, i + 1, j - 1);
  int selectJandJminus1 = getMaxSum(a, i, j - 2);
  int p2 = a[j]
    + (selectJandIplus1 < selectJandJminus1 ? selectJandIplus1
      : selectJandJminus1);

  return p1 > p2 ? p1 : p2;
 }
}

Refer : http://www.leetcode.com/2011/02/coins-in-line.html

TODO : print selcted coins in ur turn.