fork(1) download
copy 
  1. import java.util.HashMap;
  2. import java.util.Map;
  3. import java.util.NavigableSet;
  4. import java.util.TreeSet;
  5.  
  6. class LIS
  7. {
  8. 	public static void printLIS (int [] input){
  9. 		int size = input.length;
  10. 		//create an empty ordered set s
  11. 		NavigableSet<Integer> set = new TreeSet<>();
  12.  
  13.         /*
  14.         parent [i] will store the predecessor of element with index i in the
  15.         LIS ending at element with index i
  16.          */
  17. 		Map<Integer, Integer> parent = new HashMap<>();
  18.  
  19. 		for (int i=0;i<size;i++){
  20. 			set.add(input[i]);
  21.  
  22.  
  23.             /*
  24.             if element is not inserted at the end, then delete next greater element from set.
  25.              */
  26. 			if(input[i]!=set.last())
  27. 				set.remove(set.ceiling(input[i]+1));
  28.  
  29.             /*
  30.              if the element is the last, then it potentially can be part of the final answer, capture the
  31.              parent.
  32.              */
  33. 			if(set.last()==input[i])
  34. 				parent.put(input[i], set.floor(input[i]-1));
  35.  
  36.  
  37. 		}
  38. 		print(parent, set.last());
  39. 	}
  40.  
  41. 	private static void print(Map<Integer, Integer> parent, Integer lastElement){
  42. 		while (parent.get(lastElement)!=null){
  43. 			System.out.println(lastElement);
  44. 			lastElement=parent.get(lastElement);
  45. 		}
  46. 		System.out.println(lastElement);
  47. 	}
  48.  
  49. 	public static void main (String[] args) {
  50. 		int[] arr  = { 2, 6, 3, 4, 1, 2, 9, 5, 8 };
  51. 		printLIS(arr);
  52. 	}
  53. }
Success #stdin #stdout 0.04s 4386816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
8
5
4
3
2
https://ideone.com/bvpht2
language:
Java (HotSpot 12)
created:
6 years ago
visibility:
secret

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!