/* A direct translation from https://e...content-available-to-author-only...a.org/wiki/Longest_increasing_subsequence 
 *
 * by Khang Hoang Nguyen(kevinhng86)
 */

import java.util.Random;

public class Main {
    public static void main(String[] args) {
        long startTime, endTime, duration;
        int tCase = 1000000,
            lenEach = 15;

        /* Benchmark section */
        // Generate random strings, so the compiler doesn't optimize it away.
        String tests[] = randomStr(tCase, lenEach);

        startTime = System.nanoTime();
        for ( int i = 0; i < tCase; i++){
            wordInSeq(tests[i]);
        }    
        endTime = System.nanoTime();
        duration = (endTime - startTime); 

        System.out.printf("Benchmark score(ms) test with %d test cases, each random string is len %d: ", tCase, lenEach );
        System.out.printf("%d(Millisecond)", duration/1000000);
        System.out.println();
        /* End Benchmark */

        /* Result test section */ 
        System.out.println();
        System.out.println("Test Input:");
        System.out.println("xvwzzzxyxx => " + wordInSeq("xvwzzzxyxx"));
        System.out.println("abdb => " + wordInSeq("abdb"));
        System.out.println("xvwzxz => " + wordInSeq("xvwzxz"));
        /* End result test section. */ 
    }

    private static String wordInSeq(String s) {

        int P[] = new int[s.length()];
        int M[] = new int[s.length()+1];

        int L = 0;
        for (int i = 0; i < s.length(); i++ )  {
            // Binary search for the largest positive j ≤ L
            // such that X[M[j]] <= X[i]
            int lo = 1;
            int hi = L;

            while ( lo <= hi ){
                // This is equal to round up for / 2
                int mid = ((lo+hi) >> 1) + ((lo + hi) & 1);

                // This was change
                // <  : low to high no repeat
                // <= : low to high repeating
                // >  : high to low no repead
                // >= : high to low repeating 
                if (s.charAt(M[mid]) < s.charAt(i))
                    lo = mid+1;
                else
                    hi = mid-1;
            }
            // After searching, lo is 1 greater than the
            // length of the longest prefix of X[i]
            int newL = lo;

            // The predecessor of X[i] is the last index of 
            // the subsequence of length newL-1
            P[i] = M[newL-1];
            M[newL] = i;

            if (newL > L){
                // If we found a subsequence longer than any we've
                // found yet, update L
                L = newL;
            }
        }

        // Reconstruct the longest increasing subsequence
        char S[] = new char[L];
        int k = M[L];
        for (int i = L - 1; i > -1; i-- ){
            S[i] = s.charAt(k);
            k = P[k];
        }
        return new String(S);
    }

    private static String[] randomStr( int amount, int lenEach ){
        String output[] = new String[amount];
        Random random = new Random();

        for ( int i = 0; i < amount; i++){
            char temp[] = new char[lenEach];
            for ( int j = 0; j < lenEach; j++){
                temp[j] = (char)(random.nextInt(26) + 97);
            }
            output[i] = new String(temp);
        }

        return output;
    }
}