Given an array of integers, find the length of the longest subsequence such that elements in the subsequence are consecutive integers, the consecutive numbers can be in increasing order of the index.
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class LongestConsecutive {
/**
* Return the size of the maximum increasing sequence.
* @param array
* @return size of longest sequence
*/
private static int getLngIncrSeqLen(int[] array) {
int length = array.length;
int MAX_SEQ = Integer.MIN_VALUE;
/* Map with values and there index. */
Map<Integer, Set<Integer>> map = new HashMap<Integer, Set<Integer>>();
for(int i=0;i<length;i++) {
int key = array[i];
Set<Integer> set;
if(map.containsKey(key)) {
set = map.get(key);
} else {
set = new TreeSet<Integer>();
}
set.add(i);
map.put(key,set);
}
int index = 0;
for (int value : array) {
int temp = value;
int count = 1;
index++;
while(map.containsKey(++temp)) {
Set<Integer> set = map.get(temp);
if(containsGrtrIdx(set,index,length)) {
count++;
}
}
MAX_SEQ = Math.max(MAX_SEQ,count);
}
return MAX_SEQ;
}
/**
* To check the next value exist at higher index.
* @param set
* @param index
* @param length
* @return true/false.
*/
private static boolean containsGrtrIdx(Set<Integer> set, int index,int length) {
boolean result = false;
while(index<length) {
if(set.contains(index)) {
result = true;
break;
}
index++;
}
return result;
}
/**
* Driver Method
* @param args
*/
public static void main(String[] args) {
int[] array = {14,12,6,8,4,9,10,1,2,3,11,12,13,14};
int seq = getLngIncrSeqLen(array);
System.out.println(seq);
}
}
No comments:
Post a Comment