Related: Longest Arithmetic Progression SubSequence
Dynamic Programming | Set 35 (Longest Arithmetic Progression) | GeeksforGeeks
Arithmetic progression is set of numbers in which difference between two consecutive numbers is constant. For example, 1,4,7,10,13 form a arithmetic progression.
https://orajavasolutions.wordpress.com/2014/06/28/length-of-longest-arithmetic-progression/
* The function below create a matrix mat, such that
* mat[i][j] = length of longest AP with arr[i] and arr[j] as the starting elements of AP
* Initially, mat[i][j] = 2, for all i,j.Becoz, each pair of numbers is AP of length 2.
* Starting with the second last element, we do following :
* Treat each element as Middle element of AP and find the two elements (one to the left and one to the right) whose sum is 2*current_element.
* If two such elements are found, then increment mat[i][j] = mat[j][k] + 1, because we have found third element of the AP.
* Keep track of the highest value, which is our answer.
Given a sorted set, find if there exist three elements in Arithmetic Progression or not
The answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]’ and ‘set[k]’ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1. How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.
1) Initialize i as j-1 and k as j+1
2) Do following while i >= 0 and j <= n-1 ..........a) If set[i] + set[k] is equal to 2*set[j], then we are done.
……..b) If set[i] + set[k] > 2*set[j], then decrement i (do i–-).
……..c) Else if set[i] + set[k] < 2*set[j], then increment k (do k++).
https://orajavasolutions.wordpress.com/2014/06/27/finding-three-elements-in-arithmetic-progression-a-p/
O(N^2)
https://algorithmsandme.com/longest-arithmetic-progression/
// Any 2-letter series is an AP
// Here we initialize only for the last column of lookup
for (int i=0; i<n; i++)
lookup[i][n-1] = 2;
// Loop over the array and find two elements 'i' and 'k' such that i+k = 2*j
for (int j=n-2; j>=1; j--)
{
int i = j-1; // choose i to the left of j
int k = j+1; // choose k to the right of j
while (i >= 0 && k <= n-1)
{
int isAP = ( sortedArr[i] + sortedArr[k] ) - 2*sortedArr[j];
if (isAP < 0)
{
k++;
}
else if (isAP > 0)
{
i--;
}
else
{
lookup[i][j] = lookup[j][k] + 1;
maxAP = Math.max(maxAP, lookup[i][j]);
if (maxAP == lookup[i][j])
{
// Store the Arithmetic Progression's term
// And the start point of the AP
apTerm = sortedArr[j] - sortedArr[i];
apStart = i;
}
k++;
i--;
}
}
}
System.out.print("Max AP length = " + maxAP + "\n" + sortedArr[apStart] + ", ");
for (int i=apStart+1; i<n; i++)
{
if ((sortedArr[i] - sortedArr[apStart])%apTerm == 0)
System.out.print(sortedArr[i] + ", ");
}
}
X. DP 2
https://gist.github.com/gcrfelix/54c096c66177208084db0d417419677f
Question 1: Given an array, please get the length of the longest arithmetic sequence. The element order in the arithmetic sequence should be same as the element order in the array. For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7, whose elements have same order as they are in the array, and the length is 4.
O(N^2) time and space
There are n(n-1)/2 pairs out of an array with n elements. These pairs can be categorized into a set of groups, of which each group of pairs have the same difference. For example, the pairs of numbers in the array {1, 6, 3, 5, 9, 7} can be categorized into groups:
http://siyang2notleetcode.blogspot.com/2015/02/longest-arithmetic-sequenece.html
还有人在Discuss里提出一个以最大差距为一个参数的DP。基本逻辑为
opt[i][j] // 从num[0..i]的以 j 为步长的等差数列的长度。
// base case
opt[0][j] = 1
// iteration
opt[i][j] = if(num[i]-num[t] == j) opt[t][j] + 1
实际写得时候不用在Iteration部分遍历所有j，因为只需要求出num[i]-num[t]能产生的所有j就行了。
算法复杂度是 O(max(n^2, num[max]-num[min])), space 是 O(n * num[max]-num[min]))。
由于整数最大差值达到2^32，有可能空间不足以创建这个二维数组。所以这个算法有很大的漏洞。但是这个想法是对的。如果空间不足创建二维数组，可以将步长用map来记录，只记录num中可以产生的步长，将步长map到一个list上，list里存所有以该步长为间隔的两个数的集合。这样还是可以使算法复杂度达到O(n^2)， space O(n^2)的。
http://www.geeksforgeeks.org/longest-geometric-progression/
https://www.sanfoundry.com/dynamic-programming-solutions-longest-arithmetic-progression-problem/
Program/Source Code for Brute force solution
http://codercareer.blogspot.com/2014/03/no-53-longest-arithmetic-sequence.html
http://massivealgorithms.blogspot.com/2015/08/jiaxins-leetcode-longest-consecutive.html
Dynamic Programming | Set 35 (Longest Arithmetic Progression) | GeeksforGeeks
Given a set of numbers, find the Length of the Longest Arithmetic Progression (LLAP) in it.
Examples:
set[] = {1, 7, 10, 15, 27, 29}
output = 3
The longest arithmetic progression is {1, 15, 29}
set[] = {5, 10, 15, 20, 25, 30}
output = 6
The whole set is in AP
Auxiliary Space: O(n2)Time Complexity: O(n2) Auxiliary Space: O(n2) A[i], A[j] and A[k] form an AP if 2* A[j] = A[i] + A[k] where k>j and i<j. If we formulate a table where Table[i][j] is set to length of AP with first and second element as A[i] and A[j]. When j = N, value is set to 2 because every element in array forms an AP of length 2 with last element. Move up from N-1 to 0 and fill Table [i][j] bottom up. Search for i < j and k > j such that A[i], A[j] and A[k] form an AP. Then, Table[i][j] = Table[j][k] + 1 Since we are filling table bottom up and k>j; Table[j][k] would have been already calculated when we are calculating Table[i][j].
Arithmetic progression is set of numbers in which difference between two consecutive numbers is constant. For example, 1,4,7,10,13 form a arithmetic progression.
For simplicity, we have assumed that the given set is sorted. We can always add a pre-processing step to first sort the set and then apply the below algorithms.
A simple solution is to one by one consider every pair as first two elements of AP and check for the remaining elements in sorted set. To consider all pairs as first two elements, we need to run a O(n^2) nested loop. Inside the nested loops, we need a third loop which linearly looks for the more elements in Arithmetic Progression (AP). This process takes O(n3) time.
Naive solution: for all n*(n-1)/2 pairs, compute the difference, and put them into hashtable.
The idea is to create a 2D table L[n][n]. An entry L[i][j] in this table stores LLAP with set[i] and set[j] as first two elements of AP and j > i. The last column of the table is always 2. Rest of the table is filled from bottom right to top left. To fill rest of the table, j (second element in AP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an AP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.
Two numbers always from an arithmetic progression, any number from set will always from AP of length 2 with last element of set.
If formulate a table where Table[i][j] is set to length of AP with first and second element as A[i] and A[j]. When j = N, value is set to 2 as per above statement.
Now we move up from N-1 to 0 and fill Table [i][j].
We search for i < j and k>j such that A[i], A[j] and A[k] form an AP. Then,
Table[i][j] = Table[j][k] +1
Since we are filling table bottom up and k>j Table[j][k] would have been already calculated.
Create a table 'lookup' such that lookup[j][k] will give the length of the longest AP whose first two elements are arr[j] and arr[k].
Then every time another element 'i' is found in the same series, we can updated the lookup as:
lookup[i][j] = lookup[j][k] + 1;
int lenghtOfLongestAP(int set[], int n){ if (n <= 2) return n; // Create a table and initialize all values as 2. The value of // L[i][j] stores LLAP with set[i] and set[j] as first two // elements of AP. Only valid entries are the entries where j>i int L[n][n]; int llap = 2; // Initialize the result // Fill entries in last column as 2. There will always be // two elements in AP with last number of set as second // element in AP for (int i = 0; i < n; i++) L[i][n-1] = 2; // Consider every element as second element of AP for (int j=n-2; j>=1; j--) { // Search for i and k for j int i = j-1, k = j+1; while (i >= 0 && k <= n-1) { if (set[i] + set[k] < 2*set[j]) // Table[i][k]is already filled k++; // Before changing i, set L[i][j] as 2 else if (set[i] + set[k] > 2*set[j]) { L[i][j] = 2, i--; } else { // Found i and k for j, LLAP with i and j as first two // elements is equal to LLAP with j and k as first two // elements plus 1. L[j][k] must have been filled // before as we run the loop from right side L[i][j] = L[j][k] + 1; // Update overall LLAP, if needed llap = max(llap, L[i][j]); // Change i and k to fill more L[i][j] values for // current j i--; k++; } } // If the loop was stopped due to k becoming more than // n-1, set the remaining entties in column j as 2 while (i >= 0) { L[i][j] = 2; i--; } } return llap;}* The function below create a matrix mat, such that
* mat[i][j] = length of longest AP with arr[i] and arr[j] as the starting elements of AP
* Initially, mat[i][j] = 2, for all i,j.Becoz, each pair of numbers is AP of length 2.
* Starting with the second last element, we do following :
* Treat each element as Middle element of AP and find the two elements (one to the left and one to the right) whose sum is 2*current_element.
* If two such elements are found, then increment mat[i][j] = mat[j][k] + 1, because we have found third element of the AP.
* Keep track of the highest value, which is our answer.
int lengthLongesAP(int arr[], int n) { int mat[][] = new int[n][n]; int length = 0; for(int i=0;i<n;i++) for(int j=0;j<n;j++) mat[i][j] = 2; System.out.println("Triplets in AP : "); for(int j=n-2;j>0;j--) { int i=j-1, k=j+1; int x = 2*arr[j]; while(i>=0 && k<n) { /* condition : a+c = 2*b */ if(arr[i] + arr[k] == x) { System.out.println(arr[i] + " " + arr[j] + " " + arr[k]); mat[i][j] = mat[j][k] + 1; if(mat[i][j] > length) length = mat[i][j]; i--;k++; } else if(arr[i] + arr[k] < x) // a+c < 2*b, find a higher value of c by incrementing k (array is in sorted order) k++; else // a+c > 2*b, find a lower value of a by decrementing i (array is in sorted order) i--; } } System.out.println("Resultant matrix created : "); for(int i=0;i<n;i++) { System.out.println(""); for(int j=0;j<n;j++) System.out.print(mat[i][j]+" "); } return length; }The answer is true if there are 3 or more elements in AP, otherwise false.
To find the three elements, we first fix an element as middle element and search for other two (one smaller and one greater). We start from the second element and fix every element as middle element. For an element set[j] to be middle of AP, there must exist elements ‘set[i]’ and ‘set[k]’ such that set[i] + set[k] = 2*set[j] where 0 <= i < j and j < k <=n-1. How to efficiently find i and k for a given j? We can find i and k in linear time using following simple algorithm.
1) Initialize i as j-1 and k as j+1
2) Do following while i >= 0 and j <= n-1 ..........a) If set[i] + set[k] is equal to 2*set[j], then we are done.
……..b) If set[i] + set[k] > 2*set[j], then decrement i (do i–-).
……..c) Else if set[i] + set[k] < 2*set[j], then increment k (do k++).
bool arithmeticThree(int set[], int n){ // One by fix every element as middle element for (int j=1; j<n-1; j++) { // Initialize i and k for the current j int i = j-1, k = j+1; // Find if there exist i and k that form AP // with j as middle element while (i >= 0 && k <= n-1) { if (set[i] + set[k] == 2*set[j]) return true; (set[i] + set[k] < 2*set[j])? k++ : i–; } } return false;}O(N^2)
* Method 2 : Complexity (n^2) * If a,b,c are in A.P, then, 2*b = a + c * This method treats each element (except the first and last element), * as the middle element of A.P., and, then * tries to find the two elements (one to the left and one to the right) * whose sum is 2*current_element. * */ void findElementInAP_Method_2(int arr[], int n) { /* For each element (b) except the first and last element, * Find a and c (a is in the left of b, c is in the right of b), such that, * a+c = 2*b */ for(int j=1;j<n-1;j++) { int i=j-1, k=j+1; int x = 2*arr[j]; while(i>=0 && k<n) { /* condition : a+c = 2*b */ if(arr[i] + arr[k] == x) { System.out.println(arr[i] + " " + arr[j] + " " + arr[k]); i--;k++; } else if(arr[i] + arr[k] < x) // a+c < 2*b, find a higher value of c by incrementing k (array is in sorted order) k++; else // a+c > 2*b, find a lower value of a by decrementing i (array is in sorted order) i--; } } } /** * Method 1 : Complexity (n^3) * This brute force method, takes all three element groups checks * whether they are in A.P or not. */ void findElementInAP_Method_1(int arr[], int n) { for(int i=0;i<n-2;i++) for(int j=i+1;j<n-1;j++) for(int k=j+1;k<n;k++) if(Math.abs(arr[i]-arr[j]) == Math.abs(arr[j]-arr[k])) System.out.println(arr[i] + " " + arr[j] + " " + arr[k]); }
What will be the brute force solution? In any arithmetic progression, difference between any two consecutive elements should be same as the difference between first and second element. We can pick each pair of numbers from set as first two elements in AP, then scan the remaining array to find all numbers which satisfy the condition.
There are n(n-1) pairs for a set of n elements, for each pair, we linearly scan the array for more elements in AP. Overall complexity of brute force algorithm to find length of longest arithmetic progression would be
http://prismoskills.appspot.com/lessons/Dynamic_Programming/Chapter_22_-_Longest_arithmetic_progression.jspO(n3).// Any 2-letter series is an AP
// Here we initialize only for the last column of lookup
for (int i=0; i<n; i++)
lookup[i][n-1] = 2;
// Loop over the array and find two elements 'i' and 'k' such that i+k = 2*j
for (int j=n-2; j>=1; j--)
{
int i = j-1; // choose i to the left of j
int k = j+1; // choose k to the right of j
while (i >= 0 && k <= n-1)
{
int isAP = ( sortedArr[i] + sortedArr[k] ) - 2*sortedArr[j];
if (isAP < 0)
{
k++;
}
else if (isAP > 0)
{
i--;
}
else
{
lookup[i][j] = lookup[j][k] + 1;
maxAP = Math.max(maxAP, lookup[i][j]);
if (maxAP == lookup[i][j])
{
// Store the Arithmetic Progression's term
// And the start point of the AP
apTerm = sortedArr[j] - sortedArr[i];
apStart = i;
}
k++;
i--;
}
}
}
System.out.print("Max AP length = " + maxAP + "\n" + sortedArr[apStart] + ", ");
for (int i=apStart+1; i<n; i++)
{
if ((sortedArr[i] - sortedArr[apStart])%apTerm == 0)
System.out.print(sortedArr[i] + ", ");
}
}
X. DP 2
https://gist.github.com/gcrfelix/54c096c66177208084db0d417419677f
//O(n^2) time, O(n^2) space
public int longestArithmeticProgression(int[] nums) {
if (nums == null || nums.length < 2) {
return 0;
}
// key is diff, value is list of index pair with the same diff
HashMap<Integer, List<int[]>> map = new HashMap<Integer, List<int[]>>();
for (int i = 0; i < nums.length - 1; i++) { // 注意这边是i<len-1
for (int j = i + 1; j < nums.length; j++) {
int diff = nums[j] - nums[i];
if (!map.containsKey(diff))
map.put(diff, new ArrayList<int[]>());
map.get(diff).add(new int[] { i, j });
}
}
int max = 0;
for (int diff : map.keySet()) {
int[] lengths = new int[nums.length];
Arrays.fill(lengths, 1); // initialize all nums to 1
for (int[] pair : map.get(diff)) {
lengths[pair[1]] = lengths[pair[0]] + 1; // update length of this diff's Arithmetic Progression
max = Math.max(max, lengths[pair[1]]);
}
}
return max;
}
No. 53 - Longest Arithmetic SequenceQuestion 1: Given an array, please get the length of the longest arithmetic sequence. The element order in the arithmetic sequence should be same as the element order in the array. For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7, whose elements have same order as they are in the array, and the length is 4.
O(N^2) time and space
There are n(n-1)/2 pairs out of an array with n elements. These pairs can be categorized into a set of groups, of which each group of pairs have the same difference. For example, the pairs of numbers in the array {1, 6, 3, 5, 9, 7} can be categorized into groups:
Difference -1: (6, 5)
Difference 2: (1, 3), (3, 5), (5, 7)
Difference 3: (6, 9)
…
Difference 2: (1, 3), (3, 5), (5, 7)
Difference 3: (6, 9)
…
Therefore, a hash table can be defined for the groups. The key in the hash table is the difference of pairs, and the value in the hash table is a list of pairs with same difference.
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, intlengthOfNumbers)
{
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;
}
Question 2: Given an array, please get the length of the longest arithmetic sequence. The element order in the arithmetic sequence is not necessarily same as the element order in the array. For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, 7, and 9, and the length is 5.
Analysis: Different from the previous problem, there are no limitations on the order of arithmetic sequence. Consequently, we can sort the array before we try to get the maximal length of arithmetic sequences. The code is almost same as before, except for the revision that there is an additional line of code to sort the array, as listed below:
public static int GetMaxLengthOfArithmeticSequence(int[] numbers)
{
Array.Sort(numbers);
var hashTable = BuildHashTable(numbers);
return Analyze(hashTable, numbers.Length);
}
http://siyang2notleetcode.blogspot.com/2015/02/longest-arithmetic-sequenece.html
还有人在Discuss里提出一个以最大差距为一个参数的DP。基本逻辑为
opt[i][j] // 从num[0..i]的以 j 为步长的等差数列的长度。
// base case
opt[0][j] = 1
// iteration
opt[i][j] = if(num[i]-num[t] == j) opt[t][j] + 1
实际写得时候不用在Iteration部分遍历所有j，因为只需要求出num[i]-num[t]能产生的所有j就行了。
算法复杂度是 O(max(n^2, num[max]-num[min])), space 是 O(n * num[max]-num[min]))。
由于整数最大差值达到2^32，有可能空间不足以创建这个二维数组。所以这个算法有很大的漏洞。但是这个想法是对的。如果空间不足创建二维数组，可以将步长用map来记录，只记录num中可以产生的步长，将步长map到一个list上，list里存所有以该步长为间隔的两个数的集合。这样还是可以使算法复杂度达到O(n^2)， space O(n^2)的。
public int longestArithmeticSeq(int num[]){
if(num.length < 2) return num.length;
Arrays.sort(num);
int longest = 2;
int m = num[num.length-1] - num[0];
// opt is defined "the length of longest arithmetix seq in num[0..i] using j as step"
int opt[][] = new int[num.length][m+1];
// base case
for(int i = 0;i <= m;i++) opt[0][i] = 1;
// iteration
for(int i = 0;i < num.length-1;i++){
for(int j = i+1;j < num.length;j++){
opt[j][num[j]-num[i]] = opt[i][num[j]-num[i]]+1;
longest = Math.max(longest, opt[j][num[j]-num[i]]);
}
}
return longest;
} http://www.geeksforgeeks.org/longest-geometric-progression/
Given a set of numbers, find the Length of the Longest Geometrix Progression (LLGP) in it. The common ratio of GP must be an integer.
Examples:
set[] = {5, 7, 10, 15, 20, 29}
output = 3
The longest arithmetic progression is {5, 10, 20}
set[] = {3, 9, 27, 81}
output = 4
We first sort the given set. We use an auxiliary table L[n][n] to store results of subproblems. An entry L[i][j] in this table stores LLGP with set[i] and set[j] as first two elements of GP and j > i. The table is filled from bottom right to top left. To fill the table, j (second element in GP) is first fixed. i and k are searched for a fixed j. If i and k are found such that i, j, k form an GP, then the value of L[i][j] is set as L[j][k] + 1. Note that the value of L[j][k] must have been filled before as the loop traverses from right to left columns.
// Returns length of the longest GP subset of set[]int lenOfLongestGP(int set[], int n){ // Base cases if (n < 2) return n; if (n == 2) return (set[1] % set[0] == 0); // Let us sort the set first sort(set, set+n); // An entry L[i][j] in this table stores LLGP with // set[i] and set[j] as first two elements of GP // and j > i. int L[n][n]; // Initialize result (A single element is always a GP) int llgp = 1; // Initialize values of last column for (int i = 0; i < n; ++i) if (set[n-1] % set[i] == 0) L[i][n-1] = 2; else L[i][n-1] = 1; // Consider every element as second element of GP for (int j = n - 2; j >= 1; --j) { // Search for i and k for j int i = j - 1, k = j+1; while (i>=0 && k <= n-1) { // Two cases when i, j and k don't form // a GP. if (set[i] * set[k] < set[j]*set[j]) ++k; else if (set[i] * set[k] > set[j]*set[j]) { if (set[j] % set[i] == 0) L[i][j] = 2; else L[i][j] = 1; --i; } // i, j and k form GP, LLGP with i and j as // first two elements is equal to LLGP with // j and k as first two elements plus 1. // L[j][k] must have been filled before as // we run the loop from right side else { L[i][j] = L[j][k] + 1; // Update overall LLGP if (L[i][j] > llgp) llgp = L[i][j]; // Change i and k to fill more L[i][j] // values for current j --i; ++k; } } // If the loop was stopped due to k becoming // more than n-1, set the remaining entties // in column j as 1 or 2 based on divisibility // of set[j] by set[i] while (i >= 0) { if (set[j] % set[i] == 0) L[i][j] = 2; else L[i][j] = 1; --i; } } // Return result return llgp;}https://www.sanfoundry.com/dynamic-programming-solutions-longest-arithmetic-progression-problem/
Program/Source Code for Brute force solution
int llap(int n, vector<int> &a)
{if(n<=2)
return n;
int i,j,k,d;
int mxl=2;
int current;
int last;
//i will be the index of first element of the apfor(i=0;i<(n-mxl);i++)
{//j will be the index of second element of the apfor(j=i+1;j<(n-mxl+1);j++)
{//common differenced=a[j]-a[i];
last=a[j];
current=2;
for(k=j+1;k<n;k++)
{if(a[k]-last==d)
{//here is our elementcurrent++;
last=a[k];
}}mxl=max(mxl,current);
}}
return mxl;
}
http://codercareer.blogspot.com/2014/03/no-53-longest-arithmetic-sequence.html
http://massivealgorithms.blogspot.com/2015/08/jiaxins-leetcode-longest-consecutive.html
Question 3: Given an array, please get the length of the longest consecutive sequence. A consecutive sequence is an arithmetic sequence with common difference 1. The element order in the consecutive sequence is not necessarily same as the element order in the array. The solution should not cost more than O(n) time and space if the length of the input array is n. For example, in the array {1, 6, 3, 5, 9, 7}, the longest consecutive sequence is 5, 6, and 7 whose length is 3.
Analysis: The solution to solve the above problems cost O(n2) time and space. Therefore, we need a new solution to solve this problem.
O(N)
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;
}
