fork(1) download
copy 
  1. class Test {
  2.     public static void main(String[] args) {
  3.         String[] tests = {
  4.             "abdb",
  5.             "xvwzxz",
  6.             "xvwzzzxyxx",
  7.             "abczde",
  8.             "efghabcd"
  9.         };
  10.  
  11.         for(String test : tests){
  12.             System.out.println(test + "  => " + wordInSeq(test));
  13.         }
  14.     }
  15.  
  16.     private static String wordInSeq(String s) {
  17.         int[][] dp = new int[s.length()][2];
  18.         int max_index = -1;
  19.         for(int i=0;i<s.length();++i){
  20.             dp[i][0] = 1;
  21.             dp[i][1] = i;
  22.             for(int j=i-1;j>=0;--j){
  23.                 if(s.charAt(i) > s.charAt(j)){
  24.                     if(dp[i][0] < 1 + dp[j][0]){
  25.                         dp[i][0] = 1 + dp[j][0];
  26.                         dp[i][1] = j;
  27.                     }
  28.                 }
  29.             }
  30.  
  31.             if(max_index == -1 || dp[max_index][0] < dp[i][0]) max_index = i;
  32.         }
  33.  
  34.         StringBuilder res = new StringBuilder("");
  35.         int temp = max_index;
  36.         while(dp[temp][1] != temp){
  37.             res.append(s.charAt(temp));
  38.             temp = dp[temp][1];
  39.         }
  40.         res.append(s.charAt(temp));
  41.         return res.reverse().toString();
  42.     }
  43. }
Success #stdin #stdout 0.1s 36172KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
abdb  => abd
xvwzxz  => vwxz
xvwzzzxyxx  => vwxy
abczde  => abcde
efghabcd  => efgh
https://ideone.com/IpIdk7
language:
Java (HotSpot 12)
created:
5 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!