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

namespace Interview_ConsecutiveSequence
{
    class Program
    {
        public static int GetMaxLengthConsecutiveSequence(int[] numbers)
        {
            HashSet<int> set = BuildHashSet(numbers);
            return AnalyzeHashSet(set);
        }

        private static HashSet<int> BuildHashSet(int[] numbers)
        {
            var set = new HashSet<int>();
            foreach(int number in numbers)
            {
                set.Add(number);
            }

            return set;
        }

        private static int AnalyzeHashSet(HashSet<int> set)
        {
            int maxCount = 0;
            while(set.Count > 0)
            {
                int number = set.First();
                int count = 0;
                int toDelete = number;

                while(set.Remove(toDelete))
                {
                    count++;
                    toDelete++;
                }

                toDelete = number - 1;
                while(set.Remove(toDelete))
                {
                    count++;
                    toDelete--;
                }

                if(count > maxCount)
                {
                    maxCount = count;
                }
            }

            return maxCount;
        }

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

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

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


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

        private static void Test4()
        {
            int[] numbers = { 1, 3, 2, 4, 5, 19, 18, 17, 16 };
            int expected = 5;
            Test("test4", numbers, expected);
        }

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

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

dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpuYW1lc3BhY2UgSW50ZXJ2aWV3X0NvbnNlY3V0aXZlU2VxdWVuY2UKewogICAgY2xhc3MgUHJvZ3JhbQogICAgewogICAgICAgIHB1YmxpYyBzdGF0aWMgaW50IEdldE1heExlbmd0aENvbnNlY3V0aXZlU2VxdWVuY2UoaW50W10gbnVtYmVycykKICAgICAgICB7CiAgICAgICAgICAgIEhhc2hTZXQ8aW50PiBzZXQgPSBCdWlsZEhhc2hTZXQobnVtYmVycyk7CiAgICAgICAgICAgIHJldHVybiBBbmFseXplSGFzaFNldChzZXQpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgSGFzaFNldDxpbnQ+IEJ1aWxkSGFzaFNldChpbnRbXSBudW1iZXJzKQogICAgICAgIHsKICAgICAgICAgICAgdmFyIHNldCA9IG5ldyBIYXNoU2V0PGludD4oKTsKICAgICAgICAgICAgZm9yZWFjaChpbnQgbnVtYmVyIGluIG51bWJlcnMpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIHNldC5BZGQobnVtYmVyKTsKICAgICAgICAgICAgfQoKICAgICAgICAgICAgcmV0dXJuIHNldDsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIGludCBBbmFseXplSGFzaFNldChIYXNoU2V0PGludD4gc2V0KQogICAgICAgIHsKICAgICAgICAgICAgaW50IG1heENvdW50ID0gMDsKICAgICAgICAgICAgd2hpbGUoc2V0LkNvdW50ID4gMCkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgaW50IG51bWJlciA9IHNldC5GaXJzdCgpOwogICAgICAgICAgICAgICAgaW50IGNvdW50ID0gMDsKICAgICAgICAgICAgICAgIGludCB0b0RlbGV0ZSA9IG51bWJlcjsKCiAgICAgICAgICAgICAgICB3aGlsZShzZXQuUmVtb3ZlKHRvRGVsZXRlKSkKICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICBjb3VudCsrOwogICAgICAgICAgICAgICAgICAgIHRvRGVsZXRlKys7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgdG9EZWxldGUgPSBudW1iZXIgLSAxOwogICAgICAgICAgICAgICAgd2hpbGUoc2V0LlJlbW92ZSh0b0RlbGV0ZSkpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgY291bnQrKzsKICAgICAgICAgICAgICAgICAgICB0b0RlbGV0ZS0tOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIGlmKGNvdW50ID4gbWF4Q291bnQpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgbWF4Q291bnQgPSBjb3VudDsKICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgcmV0dXJuIG1heENvdW50OwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0KHN0cmluZyB0ZXN0TmFtZSwgaW50W10gbnVtYmVycywgaW50IGV4cGVjdGVkKQogICAgICAgIHsKICAgICAgICAgICAgaWYgKEdldE1heExlbmd0aENvbnNlY3V0aXZlU2VxdWVuY2UobnVtYmVycykgPT0gZXhwZWN0ZWQpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHN0cmluZy5Gb3JtYXQoInswfSBwYXNzZWQuIiwgdGVzdE5hbWUpKTsKICAgICAgICAgICAgfQogICAgICAgICAgICBlbHNlCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIENvbnNvbGUuV3JpdGVMaW5lKHN0cmluZy5Gb3JtYXQoInswfSBGQUlMRUQuIiwgdGVzdE5hbWUpKTsKICAgICAgICAgICAgfQogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0MSgpCiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBudW1iZXJzID0geyAxLCAzMDAsIDMsIDIsIDEwMSwgNCwgMTAyIH07CiAgICAgICAgICAgIGludCBleHBlY3RlZCA9IDQ7CiAgICAgICAgICAgIFRlc3QoInRlc3QxIiwgbnVtYmVycywgZXhwZWN0ZWQpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0MigpCiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBudW1iZXJzID0geyAxLCAyLCAzLCA0LCA1IH07CiAgICAgICAgICAgIGludCBleHBlY3RlZCA9IDU7CiAgICAgICAgICAgIFRlc3QoInRlc3QyIiwgbnVtYmVycywgZXhwZWN0ZWQpOwogICAgICAgIH0KCgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDMoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgNSwgNCwgMywgMiB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA0OwogICAgICAgICAgICBUZXN0KCJ0ZXN0MyIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDQoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMSwgMywgMiwgNCwgNSwgMTksIDE4LCAxNywgMTYgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gNTsKICAgICAgICAgICAgVGVzdCgidGVzdDQiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIFRlc3Q1KCkKICAgICAgICB7CiAgICAgICAgICAgIGludFtdIG51bWJlcnMgPSB7IDEsIDYsIDMsIDUsIDksIDcgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gMzsKICAgICAgICAgICAgVGVzdCgidGVzdDUiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgdm9pZCBNYWluKHN0cmluZ1tdIGFyZ3MpCiAgICAgICAgewogICAgICAgICAgICBUZXN0MSgpOwogICAgICAgICAgICBUZXN0MigpOwogICAgICAgICAgICBUZXN0MygpOwogICAgICAgICAgICBUZXN0NCgpOwogICAgICAgICAgICBUZXN0NSgpOwogICAgICAgIH0KICAgIH0KfQo=