LIS [source code]

public class LIS {
    public static int[] memo;

    public LIS(int m) {
        memo = new int[m];
        for (int i = 0; i < m; i ++)
            memo[i] = -1;
    }

    public static int dfs(int[] seq, int start) {
        if (memo[start] != -1)
            return memo[start];
        int result = 1;
        if (start == seq.length - 1) {
            memo[start] = 1;
            return 1;
        }
        int subSol = -1;
        for (int i = seq.length - 1; i > start; i--) {
            subSol = dfs(seq, i); 
            if (seq[start] < seq[i] && subSol + 1 > result)
                result = subSol + 1;
        }
        memo[start] = result;
        return result;
    }

    public static int maxLIS() {
        int result = -1; 
        for (int i = 0; i < memo.length; i++)
            if (memo[i] > result)
                result = memo[i];
        return result;
    }

    public static void main(String[] args) {
        int[] input1 = {3,5,2,6,7,4,9,1,8,0};
        LIS tester = new LIS(input1.length);
        tester.dfs(input1, 0);
        System.out.println(maxLIS());
    }
}

这个是G4G上面原来的代码: http://www.geeksforgeeks.org/longest-increasing-subsequence/

class LIS  
{  
    static int lis(int arr[],int n)  
    {  
          int lis[] = new int[n];  
          int i,j,max = 0;  

           for ( i = 0; i < n; i++ )  
              lis[i] = 1;  

           for ( i = 1; i < n; i++ )  
              for ( j = 0; j < i; j++ )   
                         if ( arr[i] > arr[j] && lis[i] < lis[j] + 1)  
                    lis[i] = lis[j] + 1;  

           for ( i = 0; i < n; i++ )  
              if ( max < lis[i] )  
                 max = lis[i];  

            return max;  
    }  

    public static void main(String args[])  
    {  
        int arr[] = { 10, 22, 9, 33, 21, 50, 41, 60 };  
            int n = arr.length;  
            System.out.println("Length of lis is " + lis( arr, n ) + "n" );  
    }  
}

注意他这里计算的方式是一个Bottom-Up, 其实我后来想想, 是更好理解的; 非要用recursion来写, 其实反而变得不是那么好理解;

当然这个问题本身背后的逻辑并不是非常的trivial: 如果有一个i比它自己前面的某一个j位置的entry要大, 并且假如把LIS_ending_at_i改成LIS_ending_at_j_followed_by_i会导致LIS length ending at i增加的话, 我们就实现这一个改变; 这个有点像图论算法里面的relaxation;

说起来是一个DP算法, 但是算法本身的核心并不是那么trivial, 而是依赖多次的重复更新;