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