Friday 12 May 2017

Longest Consecutive Subsequence


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 {
                     setnew 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

Related Posts Plugin for WordPress, Blogger...