Sunday, March 4, 2012

Largest monotonically increasing contiguous sequence


Write code for finding length of largest monotonically increasing contiguous sequence in an array of integers. Optimize it (not the usual O(n) in worst case, but a better approach in average case).


Approach:
Keep a HashMap of <A[i], length of the largest contiguous sequence of which A[i] is part of>
for each of A[i] in the array of numbers [] A.
Check if A[i]-1 is in HashMap H, if so increase its count L by 1.
check if A[i]+1 is in H, if so increase its count R by 1.
Then put A[i] in HashMap H, with count = L+R.


In the end the key with the largest count is the answer.




Code input/output:
int [] A = {2, 3, 9, 10, 11, 4, 13, 5, 15, 6, 17, 7};
largestContiguousSeq(A);
Max length of congiuous elements: 6


int [] B = {1,6,10,4,7,9,5};
largestContiguousSeq(B);
Max length of congiuous elements: 4

No comments:

Post a Comment