fork download
copy 
  1. import java.util.Arrays;
  2. /**
  3.  * Longest Increasing Sub-Sequence
  4.  * @author Prateek
  5.  */
  6. class LongestIncreasingSubsequence {
  7.  
  8. 	private static int[] LIS;  
  9. 	private static int[] sol; //Array to retrive the sequence
  10. 	static int tail=0;   //final element of sequence
  11.  
  12. 	/**
  13. 	 * Procedure to find LIS
  14. 	 * @param arr : input array
  15. 	 * @return longest value on increasing sub sequence
  16. 	 */
  17. 	public static int lis(int[] arr){
  18. 		int len = arr.length ;
  19.  
  20. 		LIS = new int[len];
  21. 		sol = new int[len] ; 
  22.  
  23. 		Arrays.fill(sol, -1);
  24.  
  25. 		LIS[0] = 1; //base case
  26. 		int MAX_LIS=1;  // default value
  27. 		int max; // gets max value for each i
  28. 		for(int i=1;i < len ; i++)
  29. 		{
  30. 			max=0;
  31. 			for(int j=0 ; j<i ; j++)
  32. 			{
  33. 				if(arr[i] > arr[j] && LIS[j] > max )
  34. 				{
  35. 						sol[i] = j ; //used to save
  36. 						max = LIS[j]; //update max for value of i
  37. 				}
  38. 			}
  39. 			LIS[i] = 1 + max ;
  40.  
  41. 			if(LIS[i] > MAX_LIS){
  42. 				MAX_LIS = LIS[i];
  43. 				tail=i;
  44. 			}
  45. 		}
  46.  
  47. 		printSequence(sol, arr);
  48. 		System.out.println("Sequence length : " + MAX_LIS);
  49. 		return MAX_LIS ;
  50. 	}
  51.  
  52.  
  53. 	public static void printSequence(int[] sol , int[] arr){
  54. 		System.out.println("Sequence : ");
  55. 		for (int j = tail; j >= 0; j = sol[j])
  56. 			System.out.print(arr[j]+"\t");
  57.  
  58. 		System.out.println();
  59. 	}
  60.  
  61. 	public static void main(String[] args) {
  62. 		int arr[] = {3, 2 , 7 , 3 , 4 , 9 , 8 , 12 , 5};
  63. 		lis(arr);
  64. 	}
  65. }
Success #stdin #stdout 0.07s 380160KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Sequence : 
12	9	4	3	2	
Sequence length : 5
https://ideone.com/k7KyC3
language:
Java (12.0.1)
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!