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)
{
Array.Sort(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, 8, 5, 7, 9, 11 };
int expected = 6;
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 = { 3, 2, 1, 3, 7, 10, 3, 6, 9, 3 };
int expected = 4;
Test("test5", numbers, expected);
}
private static void Test6()
{
int[] numbers = { 8, 3, 0, 5, 4, 9, 2 };
int expected = 4;
Test("test6", numbers, expected);
}
private static void Test7()
{
int[] numbers = { 3, 2, 1, 3, 4, 5, 3, 6, 9, 3 };
int expected = 6;
Test("test7", numbers, expected);
}
private static void Test8()
{
int[] numbers = { 2, 10, 3, 6, 4, 5, 8, 9 };
int expected = 5;
Test("test8", numbers, expected);
}
private static void Test9()
{
int[] numbers = { 1, 6, 3, 5, 9, 7 };
int expected = 5;
Test("test9", numbers, expected);
}
static void Main(string[] args)
{
Test1();
Test2();
Test3();
Test4();
Test5();
Test6();
Test7();
Test8();
Test9();
}
}
}
dXNpbmcgU3lzdGVtOwp1c2luZyBTeXN0ZW0uQ29sbGVjdGlvbnMuR2VuZXJpYzsKdXNpbmcgU3lzdGVtLkxpbnE7CgpuYW1lc3BhY2UgSW50ZXJ2aWV3X0FyaXRobWV0aWNTZXF1ZW5jZQp7CiAgICBjbGFzcyBQcm9ncmFtCiAgICB7CiAgICAgICAgaW50ZXJuYWwgY2xhc3MgUGFpcgogICAgICAgIHsKICAgICAgICAgICAgcHVibGljIGludCBGaXJzdCB7IGdldDsgc2V0OyB9CiAgICAgICAgICAgIHB1YmxpYyBpbnQgU2Vjb25kIHsgZ2V0OyBzZXQ7IH0KICAgICAgICB9CgogICAgICAgIHB1YmxpYyBzdGF0aWMgaW50IEdldE1heExlbmd0aE9mQXJpdGhtZXRpY1NlcXVlbmNlKGludFtdIG51bWJlcnMpCiAgICAgICAgewogICAgICAgICAgICBBcnJheS5Tb3J0KG51bWJlcnMpOwogICAgICAgICAgICB2YXIgaGFzaFRhYmxlID0gQnVpbGRIYXNoVGFibGUobnVtYmVycyk7CiAgICAgICAgICAgIHJldHVybiBBbmFseXplKGhhc2hUYWJsZSwgbnVtYmVycy5MZW5ndGgpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgRGljdGlvbmFyeTxpbnQsIExpc3Q8UGFpcj4+IEJ1aWxkSGFzaFRhYmxlKGludFtdIG51bWJlcnMpCiAgICAgICAgewogICAgICAgICAgICB2YXIgaGFzaFRhYmxlID0gbmV3IERpY3Rpb25hcnk8aW50LCBMaXN0PFBhaXI+PigpOwogICAgICAgICAgICBmb3IoaW50IGkgPSAwOyBpIDwgbnVtYmVycy5MZW5ndGg7ICsraSkKICAgICAgICAgICAgewogICAgICAgICAgICAgICAgZm9yKGludCBqID0gaSArIDE7IGogPCBudW1iZXJzLkxlbmd0aDsgKytqKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIFBhaXIgcGFpciA9IG5ldyBQYWlyCiAgICAgICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgICAgICBGaXJzdCA9IGksCiAgICAgICAgICAgICAgICAgICAgICAgIFNlY29uZCA9IGoKICAgICAgICAgICAgICAgICAgICB9OwoKICAgICAgICAgICAgICAgICAgICBpbnQgZGlmZiA9IG51bWJlcnNbal0gLSBudW1iZXJzW2ldOwogICAgICAgICAgICAgICAgICAgIGlmKGhhc2hUYWJsZS5LZXlzLkNvbnRhaW5zKGRpZmYpKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgaGFzaFRhYmxlW2RpZmZdLkFkZChwYWlyKTsKICAgICAgICAgICAgICAgICAgICB9CiAgICAgICAgICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgTGlzdDxQYWlyPiBuZXdWYWx1ZSA9IG5ldyBMaXN0PFBhaXI+KCk7CiAgICAgICAgICAgICAgICAgICAgICAgIG5ld1ZhbHVlLkFkZChwYWlyKTsKICAgICAgICAgICAgICAgICAgICAgICAgaGFzaFRhYmxlW2RpZmZdID0gbmV3VmFsdWU7CiAgICAgICAgICAgICAgICAgICAgfQogICAgICAgICAgICAgICAgfQogICAgICAgICAgICB9CgogICAgICAgICAgICByZXR1cm4gaGFzaFRhYmxlOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgaW50IEFuYWx5emUoRGljdGlvbmFyeTxpbnQsIExpc3Q8UGFpcj4+IGhhc2hUYWJsZSwgaW50IGxlbmd0aE9mTnVtYmVycykKICAgICAgICB7CiAgICAgICAgICAgIGludCBtYXhMZW5ndGggPSAwOwogICAgICAgICAgICBmb3JlYWNoKHZhciBrZXkgaW4gaGFzaFRhYmxlLktleXMpCiAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgIGludFtdIGxlbmd0aHMgPSBuZXcgaW50W2xlbmd0aE9mTnVtYmVyc107CiAgICAgICAgICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IGxlbmd0aE9mTnVtYmVyczsgKytpKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGxlbmd0aHNbaV0gPSAxOwogICAgICAgICAgICAgICAgfQoKICAgICAgICAgICAgICAgIGZvcmVhY2goUGFpciBwYWlyIGluIGhhc2hUYWJsZVtrZXldKQogICAgICAgICAgICAgICAgewogICAgICAgICAgICAgICAgICAgIGxlbmd0aHNbcGFpci5TZWNvbmRdID0gbGVuZ3Roc1twYWlyLkZpcnN0XSArIDE7CiAgICAgICAgICAgICAgICB9CgogICAgICAgICAgICAgICAgZm9yZWFjaCh2YXIgbGVuZ3RoIGluIGxlbmd0aHMpCiAgICAgICAgICAgICAgICB7CiAgICAgICAgICAgICAgICAgICAgaWYobGVuZ3RoID4gbWF4TGVuZ3RoKQogICAgICAgICAgICAgICAgICAgIHsKICAgICAgICAgICAgICAgICAgICAgICAgbWF4TGVuZ3RoID0gbGVuZ3RoOwogICAgICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgICAgIH0KICAgICAgICAgICAgfQoKICAgICAgICAgICAgcmV0dXJuIG1heExlbmd0aDsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdChzdHJpbmcgdGVzdE5hbWUsIGludFtdIG51bWJlcnMsIGludCBleHBlY3RlZCkKICAgICAgICB7CiAgICAgICAgICAgIGlmKEdldE1heExlbmd0aE9mQXJpdGhtZXRpY1NlcXVlbmNlKG51bWJlcnMpID09IGV4cGVjdGVkKQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShzdHJpbmcuRm9ybWF0KCJ7MH0gcGFzc2VkLiIsIHRlc3ROYW1lKSk7CiAgICAgICAgICAgIH0KICAgICAgICAgICAgZWxzZQogICAgICAgICAgICB7CiAgICAgICAgICAgICAgICBDb25zb2xlLldyaXRlTGluZShzdHJpbmcuRm9ybWF0KCJ7MH0gRkFJTEVELiIsIHRlc3ROYW1lKSk7CiAgICAgICAgICAgIH0KICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDEoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMSwgMywgMiwgNCwgOCwgNSwgNywgOSwgMTEgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gNjsKICAgICAgICAgICAgVGVzdCgidGVzdDEiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIFRlc3QyKCkKICAgICAgICB7CiAgICAgICAgICAgIGludFtdIG51bWJlcnMgPSB7IDEsIDIsIDMsIDQsIDUsIDYgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gNjsKICAgICAgICAgICAgVGVzdCgidGVzdDIiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIFRlc3QzKCkKICAgICAgICB7CiAgICAgICAgICAgIGludFtdIG51bWJlcnMgPSB7IDUsIDQsIDMsIDIsIDEgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gNTsKICAgICAgICAgICAgVGVzdCgidGVzdDMiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIFRlc3Q0KCkKICAgICAgICB7CiAgICAgICAgICAgIGludFtdIG51bWJlcnMgPSB7IDMsIDMsIDMsIDMgfTsKICAgICAgICAgICAgaW50IGV4cGVjdGVkID0gNDsKICAgICAgICAgICAgVGVzdCgidGVzdDQiLCBudW1iZXJzLCBleHBlY3RlZCk7CiAgICAgICAgfQoKICAgICAgICBwcml2YXRlIHN0YXRpYyB2b2lkIFRlc3Q1KCkKICAgICAgICB7CiAgICAgICAgICAgIGludFtdIG51bWJlcnMgPSB7IDMsIDIsIDEsIDMsIDcsIDEwLCAzLCA2LCA5LCAzIH07CiAgICAgICAgICAgIGludCBleHBlY3RlZCA9IDQ7CiAgICAgICAgICAgIFRlc3QoInRlc3Q1IiwgbnVtYmVycywgZXhwZWN0ZWQpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0NigpCiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBudW1iZXJzID0geyA4LCAzLCAwLCA1LCA0LCA5LCAyIH07CiAgICAgICAgICAgIGludCBleHBlY3RlZCA9IDQ7CiAgICAgICAgICAgIFRlc3QoInRlc3Q2IiwgbnVtYmVycywgZXhwZWN0ZWQpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0NygpCiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBudW1iZXJzID0geyAzLCAyLCAxLCAzLCA0LCA1LCAzLCA2LCA5LCAzIH07CiAgICAgICAgICAgIGludCBleHBlY3RlZCA9IDY7CiAgICAgICAgICAgIFRlc3QoInRlc3Q3IiwgbnVtYmVycywgZXhwZWN0ZWQpOwogICAgICAgIH0KCiAgICAgICAgcHJpdmF0ZSBzdGF0aWMgdm9pZCBUZXN0OCgpCiAgICAgICAgewogICAgICAgICAgICBpbnRbXSBudW1iZXJzID0geyAyLCAxMCwgMywgNiwgNCwgNSwgOCwgOSB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA1OwogICAgICAgICAgICBUZXN0KCJ0ZXN0OCIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CgogICAgICAgIHByaXZhdGUgc3RhdGljIHZvaWQgVGVzdDkoKQogICAgICAgIHsKICAgICAgICAgICAgaW50W10gbnVtYmVycyA9IHsgMSwgNiwgMywgNSwgOSwgNyB9OwogICAgICAgICAgICBpbnQgZXhwZWN0ZWQgPSA1OwogICAgICAgICAgICBUZXN0KCJ0ZXN0OSIsIG51bWJlcnMsIGV4cGVjdGVkKTsKICAgICAgICB9CiAgICAgICAgCiAgICAgICAgc3RhdGljIHZvaWQgTWFpbihzdHJpbmdbXSBhcmdzKQogICAgICAgIHsKICAgICAgICAgICAgVGVzdDEoKTsKICAgICAgICAgICAgVGVzdDIoKTsKICAgICAgICAgICAgVGVzdDMoKTsKICAgICAgICAgICAgVGVzdDQoKTsKICAgICAgICAgICAgVGVzdDUoKTsKICAgICAgICAgICAgVGVzdDYoKTsKICAgICAgICAgICAgVGVzdDcoKTsKICAgICAgICAgICAgVGVzdDgoKTsKICAgICAgICAgICAgVGVzdDkoKTsKICAgICAgICB9CiAgICB9Cn0K