最长单增子序列

发表于   |  

定义

什么是最长单增子序列（Longest Increasing Subsequence,LIS）?
一个序列S任意删除若干字符得到新序列T，则T叫做S的子序列。
一个序列S的所有子序列中，保持单调递增且长度最长的序列T，即是LIS
如序列的{-7,10,9,2,3,8,8,1}的LIS是{-7,2,3,8}

LIS的变形有以下几种：

  • 非严格定义的单调递增（最长不下降），即序列中元素可相等
  • 严格的单调递减
  • 非严格定义的单调递减（最长不上升）

以下仅以严格意义的LIS为例

0(n2) 解法

这里取最常规的 n2 算法。
当然还有其他类似的方法 以及使用 LCS 的解法。

现在有序列 S，S 的长度为 n （下标从 0 开始）
我们设 dp[i] (0 <= i <= n) 为序列 S 的前 i 个元素组成的序列的 LIS 的长度。
初始状态 dp[0] = 0
那么我们的在 dp[i] 时作出的决策是：对于每个 S[j] (0 <= j < i), 若 S[j] < S[i], 那么 dp[i] = dp[j] + 1
若不存在 S[j] < S[i], 那么 dp[i] = 1
所以可以得到递推式: dp[i] = max{dp[j] | S[j] < S[i], 0 <= j < i} + 1

求出解空间：
定义数组 pre[] 保存每个 dp[i] 的来源下标
定义数组 ans[] 为 LIS 的解空间

Java 实现：

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
52
53
54
55
56
int [] data = {1, 6, 2, 3, 5, 7, 7, 6, 9};
int [] ans;

void test() {
    int len = findLIS(data);
	System.out.println(len);
	printLIS(ans);
}

int findLIS(int [] S) { // index of S[] begin from 0
    int n = S.length;
    int max = 1; // when n = 1
    int pos = 0; ////
	int [] dp = new int [n];
	int [] pre = new int[n]; ////
	
    for (int i = 0; i < n; i++) { // initial
        dp[i] = 1;
        pre[i] = i; ////
    }
	
    for (int i = 0; i < n; i++) { // process
        for (int j = 0; j < i; j++) {
	        // (非)严格上升： S[j] <(=) S[i]
	        // (非)严格下降： S[j] >(=) S[i]
	        if (S[j] < S[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                pre[i] = j; ////
                if (dp[i] > max) {
                    max = dp[i];
                    pos = i; ////
                }
            }
        }
    }
	
	//// get LIS 
    ans = new int [max];
    for (int i = max -1; i >= 0; i--) {
        ans[i] = S[pos];
        pos = pre[pos];
    }

    return max;
}

void printLIS(int [] ans) {
    for (int i : ans) {
        System.out.print(i);
    }
}

-------------------------------------------
output:
6
123579

注释为 ’////‘ 的语句用于求LIS解空间，体现为 ans 数组

##带权 LIS

例：UVA 11790
常规的 LIS 按照个数计算，每个数权重为 1，如果序列带权的话，每次比大小后，记录 LIS 长度的数组 dp[] 加上的就是对应权值

关键代码:

1
2
3
4
5
6
7
for (int i = 0; i < num; i++) {
    inc[i] = dec[i] = w[i];
    for (int j = 0; j < i; j++) {
        if (h[i] > h [j]) inc[i] = Math.max(inc[i], inc[j]+w[i]);
        if (h[i] < h [j]) dec[i] = Math.max(dec[i], dec[j]+w[i]);
    }
}

O(nlogn) 解法

nlogn 的算法其思路同上面是基本一样的。
区别就在于，上面我们对每个S[i] 都需要遍历一遍S[j] 和 dp[j] (0 <= j < i)
如果前i项是有序的，那么通过二分查找即可优化时间复杂度。

Java 实现

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
int [] data = {1, 6, 2, 3, 5, 7, 7, 6, 9};
int [] ans; // LIS

void test2() {
	find_lis(data);
	System.out.println(ans.length);
    for (int i : ans)
    	System.out.print(i + " ");
    System.out.println();
}

void find_lis(int [] S) {
	int [] pre = new int [S.length];
    int [] b = new int [S.length]; // store the index of S in LIS
	int u, v, cntb = 0;
    b[cntb++] = 0;

    for (int i = 1; i < S.length; i++) {
        // < : strictly increasing, <= increasing
        if (S[ b[cntb - 1] ] < S[i]) {
            pre[i] = b[cntb - 1];
            b[cntb++] = i;
            continue;
        }

    	for (u = 0, v = cntb - 1; u < v;) {
            int c = (u + v) / 2;
            if (S[ b[c] ] < S[i]) u = c + 1; else v = c;
        }

        if (S[i] < S[ b[u] ]) {
            if (u > 0) pre[i] = b[u-1];
            b[u] = i;
        }
    }

    for (u = cntb, v = b[cntb-1]; --u > 0; v = pre[v]) {
    	b[u] = v;
    }

    ans = new int [cntb];
    for (int i = 0; i < cntb; i++) {
    	ans[i] = S[ b[i] ];
    }
}

nlogn 算法的内在思想还是没有理解地很深刻。

Reference

关于LIS O(n lgn)算法的一点理解
Longest Increasing Subsequence