fork(1) download
copy 
  1.  
  2. import java.util.HashMap;
  3. import java.util.Map;
  4.  
  5. /**
  6.  * User: uerturk
  7.  */
  8.  
  9. /**
  10.  * Given an int array which might contain duplicates, find the largest
  11.  * subset of it which form a sequence.
  12.  * Eg. {1,6,10,4,7,9,5}
  13.  * then answer is 4,5,6,7
  14.  * Sorting is an obvious solution. Can this be done in O(n) time
  15.  */
  16. class FindTheLongestSequence {
  17.     private int follow(int startNumber, Map<Integer, Pair<Boolean, Integer>> pairMap) {
  18.         Pair<Boolean, Integer> currentPair = pairMap.get(startNumber);
  19.         if (currentPair == null) {
  20.             return 0;
  21.         } else {
  22.             if (currentPair.getFirst()) {
  23.                 return currentPair.getSecond();
  24.             } else {
  25.                 int result = follow(startNumber + 1, pairMap) + 1;
  26.                 currentPair.setFirst(true);
  27.                 currentPair.setSecond(result);
  28.                 return result;
  29.             }
  30.         }
  31.     }
  32.  
  33.     public void longestSequence() {
  34.         int[] ints = {1, 6, 10, 4, 7, 9, 5};
  35.         // in the map first is the number, in the pair first isVisited flag, second is the score
  36.         Map<Integer, Pair<Boolean, Integer>> pairMap = new HashMap<Integer, Pair<Boolean, Integer>>();
  37.         for (Integer i : ints) {
  38.             pairMap.put(i, new Pair<Boolean, Integer>(false, 1));
  39.         }
  40.  
  41.         int[] results = new int[ints.length];
  42.         for (int i = 0; i < ints.length; i++) {
  43.             int result = follow(ints[i], pairMap);
  44.             results[i] = result;
  45.             System.out.println(ints[i] + ":" + result);
  46.         }
  47.  
  48.     }
  49.  
  50.     class Pair<First, Second> {
  51.         First first;
  52.         Second second;
  53.  
  54.         public Pair(First first, Second second) {
  55.             this.first = first;
  56.             this.second = second;
  57.         }
  58.  
  59.         public void setFirst(First first) {
  60.             this.first = first;
  61.         }
  62.  
  63.         public void setSecond(Second second) {
  64.             this.second = second;
  65.         }
  66.  
  67.         public First getFirst() {
  68.             return first;
  69.         }
  70.  
  71.         public Second getSecond() {
  72.             return second;
  73.         }
  74.  
  75.         public void set(First first, Second second) {
  76.             setFirst(first);
  77.             setSecond(second);
  78.         }
  79.     }
  80.  
  81.     public static void main(String[] args) {
  82.         new FindTheLongestSequence().longestSequence();
  83.     }
  84. }
  85.  
Success #stdin #stdout 0.07s 380224KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1:1
6:2
10:1
4:4
7:1
9:2
5:3
https://ideone.com/bA65XS
language:
Java (HotSpot 12)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!