// http://practice.geeksforgeeks.org/problems/max-possible-amount/0

using System;

public class Program

{

    public static void Main()

    {

        Console.WriteLine("Hello World");

        int[] input = new int[] { 8, 15, 3, 7 };

        int size = input.Length;

        WinningsArray = new int[size][];

        int totalSum = 0;

        for (int i = 0; i < size; i++)

        {

            WinningsArray[i] = new int[size];

            totalSum += input[i];

        }

        Console.WriteLine(MaxPossibleWinning(input, 0, size - 1, totalSum));

        for (int i = 0; i < size; i++)

        {

            for (int j = 0; j < size; j++)

            {

                Console.Write(" " + WinningsArray[i][j]);

            }

            Console.WriteLine();

        }

    }

    public static int[][] WinningsArray;

    public static int MaxPossibleWinning(int[] input, int start, int end, int totalSum)

    {

        if (WinningsArray[start][end] != 0)

        {

            return WinningsArray[start][end];

        }

        if (start == end + 1)

        {

            return UpdateWinningsArrayAndReturnMax(start, end, input[start], input[end]);

        }

        if (start == end)

        {

            return UpdateWinningsArrayAndReturnMax(start, end, input[start], input[end]);

        }

        var winningsFromLeft = totalSum - MaxPossibleWinning(input, start + 1, end, totalSum - input[start]);

        var winningsFromRight = totalSum - MaxPossibleWinning(input, start, end - 1, totalSum - input[end]);

        return UpdateWinningsArrayAndReturnMax(start, end, winningsFromLeft, winningsFromRight);

    }

    public static int UpdateWinningsArrayAndReturnMax(int start, int end, int winningsFromLeft, int winningsFromRight)

    {

        WinningsArray[start][end] = winningsFromLeft > winningsFromRight ? winningsFromLeft : winningsFromRight;

        return WinningsArray[start][end];

    }

}