fork(2) download
copy 
  1. /**
  2.  **    Java Program to implement Longest Increasing Subsequence Algorithm
  3.  **/
  4.  
  5. import java.util.Scanner;
  6.  
  7. /** Class  LongestIncreasingSubsequence **/
  8.  class  LongestIncreasingSubsequence
  9. { int fuc=0;
  10.     /** function lis **/
  11.     public int[] lis(int[] X)
  12.     {        fuc++;
  13.         int n = X.length - 1;
  14.         int[] M = new int[n + 1];  
  15.         int[] P = new int[n + 1]; 
  16.         int L = 0;
  17.  
  18.         for (int i = 1; i < n + 1; i++)
  19.         {
  20.             int j = 0;
  21.  
  22.             /** Linear search applied here. Binary Search can be applied too.
  23.                 binary search for the largest positive j <= L such that 
  24.                 X[M[j]] < X[i] (or set j = 0 if no such value exists) **/
  25.  
  26.             for (int pos = L ; pos >= 1; pos--)
  27.             {
  28.                 if (X[M[pos]] < X[i])
  29.                 {
  30.                     j = pos;
  31.                     break;
  32.                 }
  33.             }            
  34.             P[i] = M[j];
  35.             if (j == L || X[i] < X[M[j + 1]])
  36.             {
  37.                 M[j + 1] = i;
  38.                 L = Math.max(L,j + 1);
  39.             }
  40.         }
  41.  
  42.         /** backtrack **/
  43.  
  44.         int[] result = new int[L];
  45.         int pos = M[L];
  46.         for (int i = L - 1; i >= 0; i--)
  47.         {
  48.             result[i] = pos;
  49.             pos = P[pos];
  50.         }
  51.         return result;             
  52.     }
  53.  
  54.  
  55.     /** Main Function **/
  56.     public static void main(String[] args) 
  57.     {    
  58.         Scanner scan = new Scanner(System.in);
  59.  
  60.  
  61.  
  62.         int n = scan.nextInt();
  63.         int[] arr = new int[n+1];
  64.  
  65.         for (int i = 1; i <= n; i++)
  66.             arr[i] = scan.nextInt();
  67.  
  68.         LongestIncreasingSubsequence obj = new LongestIncreasingSubsequence(); 
  69.  
  70. 			 int [] result=new int[n+1];
  71. 			  int [] far=new int[n+1];
  72.       /*for (int i = 1; i <=n; i++){
  73.         result[i]=arr[i];
  74.         
  75.         }*/
  76.        // System.arraycopy( arr, 0, result, 0, arr.length );
  77.  
  78.         int t=0;
  79.  
  80.        while(true)
  81.         {if(t==n)
  82.         break;
  83.  
  84.           	int chount=0;
  85.         	for (int i = 0; i <=result.length-1; i++)
  86.         	{ //System.out.print(result[i]+" ");
  87.         	 if(arr[result[i]]!=-1)
  88.         	  arr[result[i]]=-1;
  89.         	}
  90.         	 t++;
  91.         	 	//System.out.println("");
  92.  
  93.         	 	 int k=1,fk=1;
  94.         	 	 	for (int i = 1; i <=arr.length-1; i++)
  95.         		{ 
  96.  
  97.         			if(arr[i]!=-1)
  98.         		{
  99.  
  100.         			k++;
  101.         		}
  102.         	 }
  103.         	 far=new int[k];
  104.         	for (int i = 1; i <=arr.length-1; i++)
  105.         	{ 
  106.  
  107.         			if(arr[i]!=-1)
  108.         		{
  109.         			far[fk]=arr[i];
  110.         			fk++;
  111.         		}
  112.         	 }
  113.  
  114.         		for (int i = 1; i <=arr.length-1; i++)
  115.         	 if(arr[i]==-1)
  116.         		{ 
  117.         	  		chount++;
  118.         		}
  119.         	//System.out.println("");
  120.         	if(chount==arr.length-1)
  121.         	break;
  122.         //	System.out.println("func");
  123.         	// for (int i = 1; i <=fk-1; i++)
  124.         	//  System.out.print(far[i]+" frr"+far.length );
  125.        // obj = new LongestIncreasingSubsequence(); 
  126.         	result=obj.lis(far);
  127.  
  128.         }
  129.  
  130.  
  131.         System.out.println(obj.fuc);
  132.     }
  133. }
Success #stdin #stdout 0.17s 321344KB
comments (?)
stdin
copy 
4
4 4 4 4
stdout
copy 
4
https://ideone.com/Nd2eba
language:
Java (HotSpot 12)
created:
8 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!