1. Longest Increasing Subsequence (LIS) problem
unsorted array, calculate out the maximum length of subsequence with non-decreasing order.
lis[i] = lis[j] + 1 if arr[i] > arr[j]; lis[i] is the lis with arr[i] as the last element. so to get the maximum for the whole array, we should iterate the array and find out the max(lis[i])
complexity: O(n^2)
better algorithm: O(n logn): http://en.wikipedia.org/wiki/Longest_increasing_subsequence#Efficient_algorithms
2. Longest common subsequence
f[i][j] = f[i-1][j-1]+1 if s1[i-1] == s2[j-1]
max(f[i-1][j], f[i][j-1]) else
3.
Algorithm: dynamic programming
原文：http://www.cnblogs.com/yingzhongwen/p/3542664.html