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();
}
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpuYW1lc3BhY2UgSW50ZXJ2aWV3X0FyaXRobWV0aWNTZXF1ZW5jZQp7CiAgICBjbGFzcyBQcm9ncmFtCiAgICB7CiAgICAgICAgaW50ZXJuYWwgY2xhc3MgUGFpcgogICAgICAgIHsKICAgICAgICAgICAgcHVibGljIGludCBGaXJzdCB7IGdldDsgc2V0OyB9CiAgICAgICAgICAgIHB1YmxpYyBpbnQgU2Vjb25kIHsgZ2V0OyBzZXQ7IH0KICAgICAgICB9CgogICAgICAgIHB1YmxpYyBzdGF0aWMgaW50IEdldE1heExlbmd0aE9mQXJpdGhtZXRpY1NlcXVlbmNlKGludFtdIG51bWJlcnMpCiAgICAgICAgewogICAgICAgICAgICB2YXIgaGFzaFRhYmxlID0gQnVpbGRIYXNoVGFibGUobnVtYmVycyk7CiAgICAgICAgICAgIHJldHVybiBBbmFseXplKGhhc2hUYWJsZSwgbnVtYmVycy5MZW5ndGgpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgRGljdGlvbmFyeTxpbnQsIExpc3Q8UGFpcj4+IEJ1aWxkSGFzaFRhYmxlKGludFtdIG51bWJlcnMpCiAgICAgICAgewogICAgICAgICAgICB2YXIgaGFzaFRhYmxlID0gbmV3IERpY3Rpb25hcnk8aW50LCBMaXN0PFBhaXI+PigpOwogICAgICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbnVtYmVycy5MZW5ndGg7ICsraSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZm9yKGludCBqID0gaSArIDE7IGogPCBudW1iZXJzLkxlbmd0aDsgKytqKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIFBhaXIgcGFpciA9IG5ldyBQYWlyCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBGaXJzdCA9IGksCiAgICAgICAgICAgICAgICAgICAgICAgIFNlY29uZCA9IGoKICAgICAgICAgICAgICAgICAgICB9OwoKICAgICAgICAgICAgICAgICAgICBpbnQgZGlmZiA9IG51bWJlcnNbal0gLSBudW1iZXJzW2ldOwogICAgICAgICAgICAgICAgICAgIGlmKGhhc2hUYWJsZS5LZXlzLkNvbnRhaW5zKGRpZmYpKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaGFzaFRhYmxlW2RpZmZdLkFkZChwYWlyKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgTGlzdDxQYWlyPiBuZXdWYWx1ZSA9IG5ldyBMaXN0PFBhaXI+KCk7CiAgICAgICAgICAgICAgICAgICAgICAgIG5ld1ZhbHVlLkFkZChwYWlyKTsKICAgICAgICAgICAgICAgICAgICAgICAgaGFzaFRhYmxlW2RpZmZdID0gbmV3VmFsdWU7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICByZXR1cm4gaGFzaFRhYmxlOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgaW50IEFuYWx5emUoRGljdGlvbmFyeTxpbnQsIExpc3Q8UGFpcj4+IGhhc2hUYWJsZSwgaW50IGxlbmd0aE9mTnVtYmVycykKICAgICAgICB7CiAgICAgICAgICAgIGludCBtYXhMZW5ndGggPSAwOwogICAgICAgICAgICBmb3JlYWNoKHZhciBrZXkgaW4gaGFzaFRhYmxlLktleXMpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludFtdIGxlbmd0aHMgPSBuZXcgaW50W2xlbmd0aE9mTnVtYmVyc107CiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGxlbmd0aE9mTnVtYmVyczsgKytpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGxlbmd0aHNbaV0gPSAxOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIGZvcmVhY2goUGFpciBwYWlyIGluIGhhc2hUYWJsZVtrZXldKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGxlbmd0aHNbcGFpci5TZWNvbmRdID0gbGVuZ3Roc1twYWlyLkZpcnN0XSArIDE7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgZm9yZWFjaCh2YXIgbGVuZ3RoIGluIGxlbmd0aHMpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYobGVuZ3RoID4gbWF4TGVuZ3RoKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbWF4TGVuZ3RoID0gbGVuZ3RoOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgcmV0dXJuIG1heExlbmd0aDsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdChzdHJpbmcgdGVzdE5hbWUsIGludFtdIG51bWJlcnMsIGludCBleHBlY3RlZCkKICAgICAgICB7CiAgICAgICAgICAgIGlmKEdldE1heExlbmd0aE9mQXJpdGhtZXRpY1NlcXVlbmNlKG51bWJlcnMpID09IGV4cGVjdGVkKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShzdHJpbmcuRm9ybWF0KCJ7MH0gcGFzc2VkLiIsIHRlc3ROYW1lKSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShzdHJpbmcuRm9ybWF0KCJ7MH0gRkFJTEVELiIsIHRlc3ROYW1lKSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDEoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMSwgMywgMiwgNCwgNSB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSAzOwogICAgICAgICAgICBUZXN0KCJ0ZXN0MSIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDIoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMSwgMiwgMywgNCwgNSwgNiB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA2OwogICAgICAgICAgICBUZXN0KCJ0ZXN0MiIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDMoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgNSwgNCwgMywgMiwgMSB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA1OwogICAgICAgICAgICBUZXN0KCJ0ZXN0MyIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDQoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMywgMywgMywgMyB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA0OwogICAgICAgICAgICBUZXN0KCJ0ZXN0NCIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDUoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMSwgOCwgMywgNiwgNSwgNCwgNywgMiwgOSB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA1OwogICAgICAgICAgICBUZXN0KCJ0ZXN0NSIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDYoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgOCwgMywgNiwgNSwgNCwgNywgMiB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA0OwogICAgICAgICAgICBUZXN0KCJ0ZXN0NiIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDcoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMiwgMTAsIDMsIDYsIDQsIDUsIDgsIDkgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gNDsKICAgICAgICAgICAgVGVzdCgidGVzdDciLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBzdGF0aWMgdm9pZCBNYWluKHN0cmluZ1tdIGFyZ3MpCiAgICAgICAgewogICAgICAgICAgICBUZXN0MSgpOwogICAgICAgICAgICBUZXN0MigpOwogICAgICAgICAgICBUZXN0MygpOwogICAgICAgICAgICBUZXN0NCgpOwogICAgICAgICAgICBUZXN0NSgpOwogICAgICAgICAgICBUZXN0NigpOwogICAgICAgICAgICBUZXN0NygpOwogICAgICAgIH0KICAgIH0KfQo=