using System;

namespace P22.LongerIncreasingElementsSubArray
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] intArray = { 6, 1, 4, 3, 0, 3, 6, 4, 5 };
            int[] longerSubSequence = LongerSubSequence(intArray);
            PrintIntArray(intArray);
            int index = FindBiggestElementIndex(longerSubSequence);
            string result = "}" + intArray[index];
            for (int i = index - 1; i >= 0; i--)
            {
                if (longerSubSequence[index] == longerSubSequence[i] + 1)
                {
                    if (intArray[index] > intArray[i])
                    {
                        result = result + " ," + intArray[i];
                        index = i;
                    }
                }
            }
            result += '{';
            result = InvertString(result);
            Console.WriteLine(result);


           // PrintIntArray(intArray);
            //Console.Write("result -> ");
            //PrintIntArray(longerSubSequence);
        }

        private static int[] LongerSubSequence(int[] array)
        {
            int[] len = new int[array.Length];
            for (int i = 0; i < len.Length; i++)
            {
                len[i] = 1;
            }
            for (int i = 1; i < array.Length; i++)
            {
                int prev = 0;
                int maxLen = 0;
                for (int j = 0; j < i; j++)
                {
                    if (maxLen <= len[j])
                    {
                        maxLen = len[j];
                        prev = j;
                    }
                    if (array[prev] < array[i])
                    {
                        len[i] = maxLen + 1;
                    }
                }

            }
            return len;
        }

        private static void PrintIntArray(int[] pIntArray)
        {
            for (int i = 0; i < pIntArray.Length; i++)
            {
                Console.Write("{0,5}",pIntArray[i]);
            }
            Console.WriteLine();
        }

        private static int FindBiggestElementIndex(int[] array)
        {

            int index = 0;
            int maxValue = int.MinValue;
            for (int i = 0; i < array.Length; i++)
            {
                if (array[i] > maxValue)
                {
                    maxValue = array[i];
                    index = i;
                }
            }
            return index;
        }

        public static string InvertString(string s)
        {
            char[] arr = s.ToCharArray();
            Array.Reverse(arr);
            return new string(arr);
        }
    }
}