動的計画|最長上昇文字列の問題

タイトルの説明
まず上昇文字列を定義し、任意の0に対してn個の上昇文字列を与え、任意のものを選択して綴り、綴ることができる最長上昇文字列の長さを聞きます.
構想
この問題はまず動的計画を利用する考え方を考え、動的計画の基本思想は以下の通りである.
問題の最適解はサブ問題の最適解から導き出すことができれば、サブ問題の最適解を先に解き、元の問題の最適解を構築することができる.サブ問題がより多く繰り返されると,最終サブ問題から元の問題へ底から上へ徐々に解くことができる.
この問題は2つの問題に理解できます

前n-1単語の最長上昇文字列の組み合わせが知られている場合、n番目の文字列と前n-1文字列からなる最長上昇文字列の最長上昇文字列の問題を探す.

は、前n個の文字列からなる最長上昇文字列の長さが、前n個の文字列からなる最長上昇文字列の長さ以下であることを保証する.

コード#コード#
まず、文字列ソートの問題を解決するには、前のn-1文字列からなる最長上昇文字列の長さが前のn文字列からなる最長上昇文字列の長さ以下であることを保証するには、先頭文字の小さい文字列を前に並べ、また「aaa」と「abb」を比較する際に「aaa」を前に並べなければならない.したがって,コードでは高速配列を用いて文字列配列をソートするほか,bigger関数を用いて比値判断を行った.
次に,最長上昇文字列を探す過程でhistory配列を用いて,n−1回の解の過程で最長上昇文字列を構成できる前のn−1文字列の長さを記録した.

public class LongestAscString {

    /**
     *            ，"aaaa"   "abc"  
     */
    public static boolean bigger(char[] a, char []b){

        if (a[0] > b[0]){
            //       true
            return true;
        }else if (a[0] < b[0]){
            return false;
        }else {
            //           
            if (a[a.length-1] > b[b.length-1] ){
                return true;
            }else {
                return false;
            }
        }
    }

    /**
     *           
     * @param s
     * @return
     */
    public static String[] sortFirst(String[] s, int low, int high){
        if (low < high){
            int start = low;
            int stop = high;
            String tmp = s[low];
            char[] ctmp = tmp.toCharArray();
            while (low < high){
                char[] clow = s[low].toCharArray();
                char[] chigh = s[high].toCharArray();
                while (bigger(chigh,ctmp) && low < high){
                    high--;
                    chigh = s[high].toCharArray();
                }
                s[low] = s[high];
                while (!bigger(clow,ctmp) && low < high){
                    low++;
                    clow = s[low].toCharArray();
                }
                s[high] = s[low];
            }
            s[low] = tmp;
            sort(s, start, low-1);
            sort(s, low+1, stop);
            return s;
        }else {
            return s;
        }
    }

    /**
     *           ascstring
     * @param s
     * @return
     */
    public static int longest(String[] s){
        //     
        int max = 0;
        //        
        s = sortFirst(s, 0, s.length-1);
        //                ascString  
        int[] history = new int[s.length];
        for (int i = 0; i < s.length; i++){
            // i=0     history
            if (s[i].toCharArray().length > history[i]){
                history[i] = s[i].toCharArray().length;
                if (s[i].toCharArray().length > max){
                    max = s[i].toCharArray().length;
                }
            }
            for (int j = 0; j < i; j++){
                char[] sj = s[j].toCharArray();
                char[] si = s[i].toCharArray();
                //            history         
                if (sj[sj.length-1] <= si[0] && history[j]+si.length>history[i]){
                    //   max
                    if (history[j]+si.length > max){
                        max = history[j]+si.length;
                    }
                    history[i] = history[j]+si.length;
                }
            }
        }

        return max;
    }

    public static void main(String[] args){
        String[] s = new String[]{"dddd", "aadd", "ffxz", "cv"};
        for (String a : sortFirst(s, 0, s.length-1)){
            System.out.println(a);
        }
        System.out.println(longest(s));

    }
}