动态规划和二分查找的方式求最大递增子序列

 1     public static int BiSearch(int[] A,int len,int w)
 2     {//二分查找，返回的是刚刚大于w的值的下标，这个值要被w替换掉。因为记录数组总是有序的，所以用二分查找很明智。
 3         int left=0;
 4         int right=len-1;//len是现在数组有几个元素的长度，而不是数组的长度。
 5         int middle=0;
 6         while(left<=right)
 7         {
 8             middle=(left+right)/2;
 9             if(A[middle]>w)
10                 right=middle-1;
11             else if(A[middle]<w)
12                 left=middle+1;
13             else 
14                 return middle;
15             
16         }
17         return ((A[middle]>w)?middle:middle+1);
18     }

19     public static int LIS(int [] A)
20     {
21         int [] B = new int[A.length];//B[]数组用来保存中间结果，记录长度为i的递增子序列中最大元素的最小值。
22         int i,pos=0;
23 　　　　　i
27         int len=1;
28         B[0]=A[0]; 
29         for(i=1;i<A.length;i++)
30         {//从第二个元素开始，往后比较，判断这个元素是应该直接加到B后面呢，还是替换掉B里面的某个数
31             if(A[i]>B[len-1])
32             {//如果A中数 A[i]大于B数组中的最后一个数字，直接将A[i]复制到B里，B的长度len加1
33                 B[len]=A[i];
　　　　　　　　　　　
34                 ++len;
35             }
36             else
37             {//如果A[i]不大于B数组中的最后一个数字，找到B数组中，刚刚大于A[i]的数字的下标pos，将下标为pos的值替换为A[i](较小的数)
38                 pos=BiSearch(B, len,A[i]);
39                 B[pos]=A[i];
40             }
41         }
42        return  len;//len保存的即为最大递增子序列的长度。
43        44     }

测试代码：

1 public static void main(String[] args)
2     {
3         int array[] = {2, 1, 6, 3, 5, 4, 8, 7, 9};
4         int [] res =LIS(array);
5         for(int b:res)
6             if(b!=0)
7         System.out.print(b+" ");
8         
9     }

动态规划和二分查找的方式 求最大递增子序列

动态规划和二分查找的方式求最大递增子序列