最长递增子序列longest increasing subsequence

给定数组arr，返回arr的最长递增子序列。
arr=[2,1,5,3,6,4,8,9,7]，返回的最长递增子序列为[1,3,4,8,9]。
如果arr长度为N，请实现时间复杂度为O(NlogN)的方法。
*子序列不一定连续，子串和子数组一定连续

思路 & 代码

时间复杂度为O(N^2)

产生dp数组的过程(长度就是arr的长度)

dp[i]=Max{dp[j]+1(0<=j<i， arr[j]<arr[i])}

  • dp[i]表示以i结尾的数组的最长子序列的长度
  • dp[0] = 1
  • 找到大于当前值i的位置j，dp[i] = dp[j]+1
  • 找不到大于当前值i的位置j，dp[i] = 1

找到LIS,找到dp的情况下

  • dp中的最大值就是子序列的长度
  • dp中最大值对应的arr就是子序列中的一个
  • 倒叙找到出比前面值arr[i]小的并且dp[i]=dp[j]+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
public static int[] getdp1(int[] arr) {
	// dp[i]表示以i结尾的最长的子序列长度
	int[] dp = new int[arr.length];
	dp[0] = 1;
	for (int i = 1; i < dp.length; i++) {
		if (arr[i] > arr[i - 1]) {
			dp[i] = dp[i - 1] + 1;
		} else {
			for (int j = i - 1; j >= 0; j--) {
				if (arr[j] <= arr[i]) {
					dp[i] = dp[j] + 1;
					break;
				}
			}
			if (dp[i] == 0) {
				dp[i] = 1;
			}
		}
	}
	return dp;
}
public static int[] generateLIS(int[] arr, int[] dp) {
	// dp中的最大值
	int index = 0;
	// LIS的长度
	int len = 1;
	for (int i = 1; i < dp.length; i++) {
		if (dp[index] < dp[i]) {
			index = i;
			len++;
		}
	}
	int[] res = new int[len];
	res[--len] = arr[index];
	for (int i = index - 1; i >= 0; i--) {
		if (arr[i] < arr[index] && dp[i] + 1 == dp[index]) {
			res[--len] = arr[i];
			index = i;
		}
	}
	return res;
}
public static int[] lis1(int[] arr) {
	if (arr == null || arr.length == 0) {
		return null;
	}
	int[] dp = getdp1(arr);
	return generateLIS(arr, dp);
}

时间复杂度O(N*logN)

从上面的计算dp过程可以看出，重复访问以前计算的dp值，会降低效率
因此添加一个ends数组，二分计算
ends[i]表示当前计算状态下，长度为i+1的LIS的最后结尾字符的最小值，计算ends的过程是与计算dp的过程同步的，
right是ends中的有效范围的右边界，表示[0,right]范围内是有效的ends，其余是[ends+1,arr.length]是无效的

时间复杂度O(N*logN)生成dp数组的过程是利用二分查找来进行的优化。

  • 生成一个长度为N的数组ends，初始时ends[0]=arr[0]，其他位置上的值为0。
  • 生成整型变量right，初始时right=0。

在从左到右遍历arr数组的过程中，求解dp[i]的过程需要使用ends数组和right变量
遍历的过程中， ends[0..right]为有效区， ends[right+1..N-1]为无效区。
对于有效区上的位置b，如果有ends[b]==c，则表示遍历到目前为止，在所有长度为b+1的递增序列中，最小的结尾数是c。无效区的位置则没有意义。

例如arr=[2,1,5,3,6,4,8,9,7]，初始时dp[0]=1， ends[0]=2， right=0。
ends[0..0]为有效区，ends[0]==2的含义是，在遍历过arr[0]之后，所有长度为1的递增序列中(此时只有[2])，最小的结尾数是2。
之后的遍历继续用这个例子来说明求解过程。

1，遍历到arr[1]==1。 ends有效区=ends[0..0]=[2]，在有效区中找到最左边的大于等于arr[1]的数。
发现是ends[0]，表示以arr[1]结尾的最长递增序列只有arr[1]，所以令dp[1]=1。
然后令ends[0]=1，因为遍历到目前为止，在所有长度为1的递增序列中，最小的结尾数是1而不再是2了。

2，遍历到arr[2]==5。 ends有效区=ends[0..0]=[1]，在有效区中找到最左边的大于等于arr[2]的数。
发现没有这样的数，表示以arr[2]结尾的最长递增序列长度=ends有效区长度+1，所以令dp[2]=2。
ends整个有效区都没有例arr[2]更大的数，说明发现了例ends有效区长度更长的递增序列，于是把有效区扩大， ends有效区=ends[0..1]=[1,5]。

3，遍历到arr[3]==3。 ends有效区=ends[0..1]=[1,5]，在有效区中用二分法找到最左边的大于等于arr[3]的数。
发现是ends[1]，表示以arr[3]结尾的最长递增序列长度为2，所以令dp[3]=2。然后令ends[1]=3，因为遍历到目前为止，在所有长度为2的递增序列中，最小的结尾数是3而不再是5了。

4，遍历到arr[4]==6。 ends有效区=ends[0..1]=[1,3]，在有效区中用二分法找到最左边的大于等于arr[4]的数。
发现没有这样的数，表示以arr[4]结尾的最长递增序列长度=ends有效区长度+1，所以令dp[4]=3。 ends整个有效区都没有例arr[4]更大的数，说明发现了例ends有效区长度更长的递增序列，于是把有效区扩大， ends有效区=ends[0..2]=[1,3,6]。

5，遍历到arr[5]==4。 ends有效区=ends[0..2]=[1,3,6]，在有效区中用二分法找到最左边的大于等于arr[5]的数。
发现是ends[2]，表示以arr[5]结尾的最长递增序列长度为3，所以令dp[5]=3。然后令ends[2]=4，表示在所有长度为3的递增序列中，最小的结尾数变为4。

6，遍历到arr[6]==8。 ends有效区=ends[0..2]=[1,3,4]，在有效区中用二分法找到最左边的大于等于arr[6]的数。
发现没有这样的数，表示以arr[6]结尾的最长递增序列长度=ends有效区长度+1，所以令dp[6]=4。 ends整个有效区都没有例arr[6]更大的数，说明发现了例ends有效区长度更长的递增序列，于是把有效区扩大， ends有效区=ends[0..3]=[1,3,4,8]。

7，遍历到arr[7]==9。 ends有效区=ends[0..3]=[1,3,4,8]，在有效区中用二分法找到最左边的大于等于arr[7]的数。
发现没有这样的数，表示以arr[7]结尾的最长递增序列长度=ends有效区长度+1，所以令dp[7]=5。 ends整个有效区都没有例arr[7]更大的数，于是把有效区扩大， ends有效区=ends[0..5]=[1,3,4,8,9]。

8，遍历到arr[8]==7。 ends有效区=ends[0..5]=[1,3,4,8,9]，在有效区中用二分法找到最左边的大于等于arr[8]的数。
发现是ends[3]，表示以arr[8]结尾的最长递增序列长度为4，所以令dp[8]=4。然后令ends[3]=7，表示在所有长度为4的递增序列中，最小的结尾数变为7。

具体过程请参看如下代码中的getdp2方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public static int[] getdp2(int[] arr) {
	int[] dp = new int[arr.length];
	int[] ends = new int[arr.length];
	ends[0] = arr[0];
	dp[0] = 1;
	int right = 0;
	// 二分中的左中右
	int l = 0;
	int r = 0;
	int m = 0;
	for (int i = 1; i < arr.length; i++) {
		l = 0;
		r = right;
		// 二分找到arr[i]应该在该数列的位置
		while (l <= r) {
			m = (l + r) / 2;
			if (arr[i] > ends[m]) {
				l = m + 1;
			} else {
				r = m - 1;
			}
		}
		// 如果arr[i]比ends[right]还大，那么其位置l是right+1
		// 更新right，即ends的有效区域
		right = Math.max(right, l);
		ends[l] = arr[i];
		dp[i] = l + 1;
	}
	return dp;
}