using System;
using System.Collections.Generic;
using System.Linq;

namespace Interview_ArithmeticSequence
{
    class Program
    {
        internal class Pair
        {
            public int First { get; set; }
            public int Second { get; set; }
        }

        public static int GetMaxLengthOfArithmeticSequence(int[] numbers)
        {
            var hashTable = BuildHashTable(numbers);
            return Analyze(hashTable, numbers.Length);
        }

        private static Dictionary<int, List<Pair>> BuildHashTable(int[] numbers)
        {
            var hashTable = new Dictionary<int, List<Pair>>();
            for(int i = 0; i < numbers.Length; ++i)
            {
                for(int j = i + 1; j < numbers.Length; ++j)
                {
                    Pair pair = new Pair
                    {
                        First = i,
                        Second = j
                    };

                    int diff = numbers[j] - numbers[i];
                    if(hashTable.Keys.Contains(diff))
                    {
                        hashTable[diff].Add(pair);
                    }
                    else
                    {
                        List<Pair> newValue = new List<Pair>();
                        newValue.Add(pair);
                        hashTable[diff] = newValue;
                    }
                }
            }

            return hashTable;
        }

        private static int Analyze(Dictionary<int, List<Pair>> hashTable, int lengthOfNumbers)
        {
            int maxLength = 0;
            foreach(var key in hashTable.Keys)
            {
                int[] lengths = new int[lengthOfNumbers];
                for (int i = 0; i < lengthOfNumbers; ++i)
                {
                    lengths[i] = 1;
                }

                foreach(Pair pair in hashTable[key])
                {
                    lengths[pair.Second] = lengths[pair.First] + 1;
                }

                foreach(var length in lengths)
                {
                    if(length > maxLength)
                    {
                        maxLength = length;
                    }
                }
            }

            return maxLength;
        }

        private static void Test(string testName, int[] numbers, int expected)
        {
            if(GetMaxLengthOfArithmeticSequence(numbers) == expected)
            {
                Console.WriteLine(string.Format("{0} passed.", testName));
            }
            else
            {
                Console.WriteLine(string.Format("{0} FAILED.", testName));
            }
        }

        private static void Test1()
        {
            int[] numbers = { 1, 3, 2, 4, 5 };
            int expected = 3;
            Test("test1", numbers, expected);
        }

        private static void Test2()
        {
            int[] numbers = { 1, 2, 3, 4, 5, 6 };
            int expected = 6;
            Test("test2", numbers, expected);
        }

        private static void Test3()
        {
            int[] numbers = { 5, 4, 3, 2, 1 };
            int expected = 5;
            Test("test3", numbers, expected);
        }

        private static void Test4()
        {
            int[] numbers = { 3, 3, 3, 3 };
            int expected = 4;
            Test("test4", numbers, expected);
        }

        private static void Test5()
        {
            int[] numbers = { 1, 8, 3, 6, 5, 4, 7, 2, 9 };
            int expected = 5;
            Test("test5", numbers, expected);
        }

        private static void Test6()
        {
            int[] numbers = { 8, 3, 6, 5, 4, 7, 2 };
            int expected = 4;
            Test("test6", numbers, expected);
        }

        private static void Test7()
        {
            int[] numbers = { 2, 10, 3, 6, 4, 5, 8, 9 };
            int expected = 4;
            Test("test7", numbers, expected);
        }

        static void Main(string[] args)
        {
            Test1();
            Test2();
            Test3();
            Test4();
            Test5();
            Test6();
            Test7();
        }
    }
}