ランダムな数列から昇順になってる数列を抽出する

例えば次のようなランダムな数列(同じ数字はない)から昇順になっている数列を抽出する。

2 0 5 7 1 3 9 6 4 8

そうすると

2 5 7 9

とか

0 1 3 4 8

とかが得られる。そういう数列の中で、もっとも長いものを得る。

public static void main(String[] d){
    //ランダムな数列の作成
    List<Integer> values = new ArrayList<Integer>();
    for(int i = 0; i < 10; ++i){
        values.add(i);
    }
    Collections.shuffle(values);
    //作成した数列を表示
    for(int n : values){
        System.out.print(n + " ");
    }
    System.out.println();

    List<List<Integer>> asc = new ArrayList<List<Integer>>();
    List<Integer> l = new ArrayList<Integer>();
    l.add(values.get(0));
    asc.add(l);

    //asc.add(new ArrayList<Integer>());
    for(int n : values){
        for(int i = 0; i < asc.size(); ++i){
            List<Integer> cur = asc.get(i);
            if(cur.get(cur.size() - 1) < n){
                //最後の要素よりも大きい場合
               if(i >= asc.size() - 1){
                   //一番最後の数列なら、ひとつ増やした数列を追加
                    List<Integer> neo = 
                        (List<Integer>) ((ArrayList<Integer>)cur).clone();
                   neo.add(n);
                   asc.add(neo);
               }else{
                   //一番最後の数列じゃないときは次の数列の最後と比較
                    List<Integer> next = asc.get(i + 1);
                    if(next.get(next.size() - 1) > n){
                        //次の数列の最後よりも小さい場合、数列を入れ替え
                        List<Integer> neo = 
                            (List<Integer>) ((ArrayList<Integer>)cur).clone();
                       neo.add(n);
                       asc.set(i + 1, neo);
                    }
               }
            }else{
                //最後の要素よりも小さいとき
                if(cur.size() == 1 || cur.get(cur.size() - 2) < n){
                    //要素がひとつか、最後から２番目の要素よりも大きいときは、要素を入れ替え
                    cur.set(cur.size() - 1, n);
                }
            }

        }
    }
    //一番最後の数列が一番長い昇順数列
    List<Integer> last = asc.get(asc.size() - 1);
    //結果表示
    for(int n : last){
        System.out.print(n + " ");
    }
    System.out.println();
}

アルゴリズムは、この本にのってた。この本はいろいろな分野の新しいアルゴリズムが載ってて面白いです。

アルゴリズム・サイエンス:出口からの超入門 (アルゴリズム・サイエンスシリーズ 2―超入門編)