最長遞增子序列問題 LIS(longest increasing subsequence) 例如

給定一個數(shù)列，長度為N，
求這個數(shù)列的最長上升（遞增）子數(shù)列（LIS）的長度.
以
1, 7, 2, 8, 3, 4
為例。
這個數(shù)列的最長遞增子數(shù)列是 1 2 3 4，長度為4；
次長的長度為3， 包括 1 7 8; 1 2 3 等.

設(shè)數(shù)組為：arr
設(shè) foo(k) 為：以數(shù)列中第k項 (為了與java數(shù)組邏輯一致，這里的k從0開始計算) 結(jié)尾的最長遞增子序列的長度
則：

foo(0) == 1 
foo(k) == max(arr[k]>arr[0]?foo(0)+1:foo(0),
              arr[k]>arr[1]?foo(1)+1:foo(1) , 
              ... ,
              arr[k]>arr[k-1]?foo(k-1)+1:foo(k-1))

java代碼

public class LISDemo {
    public static void main(String[] args){
        int[] arr = new int[10];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);
        }
        System.out.println("數(shù)組"+Arrays.toString(arr));
        long time = System.currentTimeMillis();
        System.out.println("結(jié)果: "+foo(arr, arr.length-1));
        System.out.println("耗時: "+(System.currentTimeMillis()-time));
    }
    private static int foo(int[] arr,int end){
        if (end==0) {
            return 1;
        }
        int len = 0;
        for (int i = 0; i < end; i++) {
            int temp = foo(arr,i);
            len = Math.max(len,arr[end]>arr[i]?temp+1:temp);
        }
        return len;
    }
}

這段代碼能計算出正確的結(jié)果，但是存在問題：
要計算 foo(n)必須先得到 foo(0)~foo(n-1)的值
要計算 foo(n-1)必須先得到 foo(0)~foo(n-2)的值
...
以此類推，可以把他畫成一顆多叉樹，時間復(fù)雜度達(dá)到O(2^n)

運行這段代碼就會發(fā)現(xiàn) 每當(dāng)數(shù)組長度+1 運行耗時大致翻倍，數(shù)組長度為幾十的時候，運行時間已經(jīng)無法容忍的長了。

以foo(3)為例，可以畫成下面這棵樹

可以發(fā)現(xiàn)，相同參數(shù)的方法被重復(fù)計算了多遍，我們可以建立一個hashmap把參數(shù)和對應(yīng)的值存入其中，當(dāng)結(jié)果已經(jīng)計算過，就直接從hashmap中取出結(jié)果不再計算，修改代碼為如下,保留了原來的方法做個對比，執(zhí)行效率天差地別:

public class LISDemo {
    public static void main(String[] args){
        int[] arr = new int[31];
        Random random = new Random();
        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt(100);
        }
        System.out.println("數(shù)組"+Arrays.toString(arr));
        LIS lis = new LIS(arr);

        long time = System.currentTimeMillis();
        System.out.println("結(jié)果1: "+lis.foo());
        System.out.println("耗時1: "+(System.currentTimeMillis()-time));

        time = System.currentTimeMillis();
        System.out.println("結(jié)果2: "+foo(arr, arr.length-1));
        System.out.println("耗時2: "+(System.currentTimeMillis()-time));
    }
    // 最長遞增子序列 longest increasing subsequence
    private static class LIS{
        int[] arr;
        HashMap<Integer,Integer> values = new HashMap<>();

        LIS(int[]arr){
            this.arr = arr;
        }
        int foo(){
            return foo(arr,arr.length-1);
        }
        private int foo(int[] arr,int end){
            Integer value = values.get(end);
            if (value != null) {
                return value;
            }
            if (end==0) {
                values.put(0,1);
                return 1;
            }
            int len = 0;
            for (int i = 0; i < end; i++) {
                int temp = foo(arr,i);
                len = Math.max(len,arr[end]>arr[i]?temp+1:temp);
            }
            values.put(end,len);
            return len;
        }

    }
    private static int foo(int[] arr,int end){
        if (end==0) {
            return 1;
        }
        int len = 0;
        for (int i = 0; i < end; i++) {
            int temp = foo(arr,i);
            len = Math.max(len,arr[end]>arr[i]?temp+1:temp);
        }
        return len;
    }
}