正文
Longest Increasing Subsequence的两种算法
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
问题描述:给出一个序列a1,a2,a3,a4,a5,a6,a7….an,求它的一个子序列（设为s1,s2,…sn），使得这个子序列满足这样的性质，s1<s2<s3<…<sn并且这个子序列的长度最长。简称LIS。
例如，对于数组[10, 9, 2, 5, 3, 7, 101, 18]，它的最长递增子序列为[2,3,7,101]，长度为4。当然最长递增子序列不止一个，例如[2,5,7,101],[2,5,7,18]都符合要求。
1.时间复杂度:O(n^2)
对于序列A(a1,a2,a3…..an)，以序列中am元素为最小值的递增序列，只与am-1，am-2，……an有关，与am之前的元素无关，因此我们可以由后向前依次求出以每个元素为起始的最长递增序列。我们用一个数组flag存储最长递增子序列的长度，若i<j,A[i] < A[j],则flag[i] = max(flag[x], j <= x <= A.length) + 1。
1: public int lengthOfLIS(int[] nums) {
2: if (nums == null || nums.length == 0)
3: return 0;
4: int[] flag = new int[nums.length];
5: Arrays.fill(flag,1);
6: int maxLength = 1;
7: for (int i =nums.length - 2; i >= 0; i--){
8: int maxTemp = flag[i];
9: for (int j = i+1; j < nums.length;j++){
10: if (nums[i] < nums[j]){
11: maxTemp = maxTemp > flag[j] + 1 ? maxTemp : flag[j] + 1;
12: }
13: }
14: flag[i] = maxTemp;
15: maxLength = maxLength > flag[i] ? maxLength: flag[i];
16: }
17: return maxLength;
18: }
2.时间复杂度O(nlogN)
我们定义一个数组dp[]，dp[i]表示长度为i的序列中最小的元素的值。例如对于序列A[10, 9, 2, 5, 3, 7, 101, 18]，我们依次扫描每个元素，
首先对于A[0] = 10 , 我们可以得dp[1] = 10 ,表示序列长度为1的最小元素为10，此时序列为10，
对于A[1] = 9, 因为A[1] < dp[1]，所以dp[1] = 9，此时序列为9
对于A[2] = 2, 因为A[2] < dp[1]，所以dp[1] = 2，此时序列为2
对于A[3] = 5, 因为A[3] > dp[1]，所以dp[2] = 5，此时序列为2,5
对于A[4] = 3, 因为A[4] < dp[2]，所以dp[2] = 3，此时序列为2,3
对于A[5] = 7, 因为A[5] > dp[2]，所以dp[3] = 7，此时序列为2,3,7
对于A[6] = 101, 因为A[6] > dp[3]，所以dp[3] = 101，此时序列为2,3,7,101
对于A[7] = 18, 因为A[7] < dp[3]，所以dp[3] = 18，此时序列为2,5,7,18
所以最长递增子序列的长度为4
1: int[] dp = new int[nums.length];
2: int len = 0;
3:
4: for(int x : nums) {
5: int i = Arrays.binarySearch(dp, 0, len, x);
6: if(i < 0) i = -(i + 1);
7: dp[i] = x;
8: if(i == len) len++;
9: }
10:
11: return len;
