最长递增子序列

?

求数组中最长递增子序列

写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。

例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6。

public class LongestIncreasingSequence {/** *求数组中最长递增子序列              写一个时间复杂度尽可能低的程序，求一个一维数组（N个元素）中的最长递增子序列的长度。              例如：在序列1，-1，2，-3，4，-5，6，-7中，其最长的递增子序列为1，2，4，6 */public static void main(String[] args) {int[] A = {1,-1,2,-3,4,-5,6,-7};LAS(A);}public static int LAS(int[] A){int length = A.length;int B[] = new int[length];B[0] = 1;int max = 1;for(int i=1;i<length;i++){int _max = 0;  //记录当前元素中比它小的元素的B[i]值最大的一个，这里只能设置为0而不能设置为1 int index = i;  //找出当前元素中比它小的元素，并比较B[i]值，记录最大的B[i]值的索引for(int j=i-1;j>=0;j--){if(A[j]<A[i] && B[j] > _max){_max = B[j];index = j;}}if(index == i)   //索引没变，前面没有比它小的元素了，则值为1B[i] = 1;elseB[i] = B[index] + 1;   //索引变了，则+1if(B[i] > max)max = B[i];}for(int i=0;i<length;i++)System.out.print(B[i]+ " ");System.out.println("\nThe Max Length is : " + max);return max;}}