fork download
copy 
  1. /* A direct translation from https://e...content-available-to-author-only...a.org/wiki/Longest_increasing_subsequence 
  2.  *
  3.  * by Khang Hoang Nguyen(kevinhng86)
  4.  */
  5.  
  6. import java.util.Random;
  7.  
  8. public class Main {
  9.     public static void main(String[] args) {
  10.         long startTime, endTime, duration;
  11.         int tCase = 1000000,
  12.             lenEach = 15;
  13.  
  14.         /* Benchmark section */
  15.         // Generate random strings, so the compiler doesn't optimize it away.
  16.         String tests[] = randomStr(tCase, lenEach);
  17.  
  18.         startTime = System.nanoTime();
  19.         for ( int i = 0; i < tCase; i++){
  20.             wordInSeq(tests[i]);
  21.         }    
  22.         endTime = System.nanoTime();
  23.         duration = (endTime - startTime); 
  24.  
  25.         System.out.printf("Benchmark score(ms) test with %d test cases, each random string is len %d: ", tCase, lenEach );
  26.         System.out.printf("%d(Millisecond)", duration/1000000);
  27.         System.out.println();
  28.         /* End Benchmark */
  29.  
  30.         /* Result test section */ 
  31.         System.out.println();
  32.         System.out.println("Test Input:");
  33.         System.out.println("xvwzzzxyxx => " + wordInSeq("xvwzzzxyxx"));
  34.         System.out.println("abdb => " + wordInSeq("abdb"));
  35.         System.out.println("xvwzxz => " + wordInSeq("xvwzxz"));
  36.         /* End result test section. */ 
  37.     }
  38.  
  39.     private static String wordInSeq(String s) {
  40.  
  41.         int P[] = new int[s.length()];
  42.         int M[] = new int[s.length()+1];
  43.  
  44.         int L = 0;
  45.         for (int i = 0; i < s.length(); i++ )  {
  46.             // Binary search for the largest positive j ≤ L
  47.             // such that X[M[j]] <= X[i]
  48.             int lo = 1;
  49.             int hi = L;
  50.  
  51.             while ( lo <= hi ){
  52.                 // This is equal to round up for / 2
  53.                 int mid = ((lo+hi) >> 1) + ((lo + hi) & 1);
  54.  
  55.                 // This was change
  56.                 // <  : low to high no repeat
  57.                 // <= : low to high repeating
  58.                 // >  : high to low no repead
  59.                 // >= : high to low repeating 
  60.                 if (s.charAt(M[mid]) < s.charAt(i))
  61.                     lo = mid+1;
  62.                 else
  63.                     hi = mid-1;
  64.             }
  65.             // After searching, lo is 1 greater than the
  66.             // length of the longest prefix of X[i]
  67.             int newL = lo;
  68.  
  69.             // The predecessor of X[i] is the last index of 
  70.             // the subsequence of length newL-1
  71.             P[i] = M[newL-1];
  72.             M[newL] = i;
  73.  
  74.             if (newL > L){
  75.                 // If we found a subsequence longer than any we've
  76.                 // found yet, update L
  77.                 L = newL;
  78.             }
  79.         }
  80.  
  81.         // Reconstruct the longest increasing subsequence
  82.         char S[] = new char[L];
  83.         int k = M[L];
  84.         for (int i = L - 1; i > -1; i-- ){
  85.             S[i] = s.charAt(k);
  86.             k = P[k];
  87.         }
  88.         return new String(S);
  89.     }
  90.  
  91.     private static String[] randomStr( int amount, int lenEach ){
  92.         String output[] = new String[amount];
  93.         Random random = new Random();
  94.  
  95.         for ( int i = 0; i < amount; i++){
  96.             char temp[] = new char[lenEach];
  97.             for ( int j = 0; j < lenEach; j++){
  98.                 temp[j] = (char)(random.nextInt(26) + 97);
  99.             }
  100.             output[i] = new String(temp);
  101.         }
  102.  
  103.         return output;
  104.     }
  105. }
Success #stdin #stdout 0.74s 181772KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Benchmark score(ms) test with 1000000 test cases, each random string is len 15: 362(Millisecond)

Test Input:
xvwzzzxyxx => vwxy
abdb => abd
xvwzxz => vwxz
https://ideone.com/4ZBwda
language:
Java (HotSpot 12)
created:
6 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!