最长递增子序列

求一个一维数组中的最长递增子序列的长度

比如，在序列{1, -1, 2, -3, 4, -5, 6, -7}中，其最长的递增子序列为1,2,4,6

思路: 编程之美上的题，也是蛮经典的动态规划题。思路还是去找规律，我们拿LCS来表示最长递增子序列的长度

第一个数1，则LCS(1)=1, 因为就一个数嘛

第二个数-1, LCS(1,-1)=1, 因为-1对于1来说不是递增的

第三个数2, LCS(1,-1,2)=2, 因为2对于前两个数是递增的

所以规律是 LCS(i) = if a[i] > a[0...i-1] => max(1, LCS(1...i-1)) + 1 就是如果a[i]的值大于数组下标在0到i-1之间的全部数, 且max(1, LCS(1...i-1))+1>LCS(i)

 1 void findLCS01(int[] array){
 2         int len = array.length;
 3         int[] LIS = new int[len];
 4         
 5         for(int i = 0; i < len; i++){
 6             LIS[i] = 1;
 7             for(int j = 0; j<i; j++){
 8                 if(array[i] > array[j] && LIS[j] + 1 > LIS[i]){
 9                     LIS[i] = LIS[j] + 1;
10                 }
11             }
12         }
13         
14         show(LIS);
15     }

上述的方法需要嵌套内循环，当遍历到a[i]元素时，需要对0到i-1之间的元素，依次判断是否小于当前a[i]元素，并且找出最大的LCS值，将其加一付给LCS[i], 时间复杂度是o(n^2)

为了降低时间复杂度，编程之美上的解决方法是对i之前的元素进行快速排序，这样就不用每次都去遍历他们，我的想法是，可以增加一个数组max，max[i-1]保存的是从0到i-1之间遇到的最大元素，数组LCS, LCS[i]保存0到i之间的最大值, 这样每次只需比较a[i]与max[i-1]即可, 如果a[i]>max[i-1] 则max[i]=a[i]然后再去判断LCS的值，否则LCS[i]沿用LCS[i-1], max[i]沿用max[i-1]

 1 void findLCS02(int[] array){
 2         int len = array.length;
 3         
 4         if(len <= 0) return;
 5         if(len <= 1) return;
 6         
 7         int[] LCS = new int[len];
 8         int[] max = new int[len];
 9         
10         LCS[0] = 1;
11         max[0] = array[0];
12         
13         for(int i = 1; i < len; i++){
14             LCS[i] = 1;
15             if(array[i] > max[i-1]){
16                 max[i] = array[i];
17                 if(LCS[i-1] + 1 > LCS[i]){
18                     LCS[i] = LCS[i-1] + 1;
19                 }
20             }else{
21                 LCS[i] = LCS[i-1];
　　　　　　　　　　　max[i] = max[i-1];
22             }
23         }
24         
25         show(LCS);
26     }

这样时间复杂度将为o(n), 用空间换时间了