Longest Increasing Subsequence，LIS， 最长上升子序列
题目
给定n个数字的序列，如11，3，6，9，13，8，问最长的上升序列上升子序列是什么。
上升序列，分为严格单调递增序列和单调不减序列。前者需满足序列L中，i<j, L[i]<L[j]，而后者可取等号。
解题思路
递增的判断都是在原序列末尾元素基础上进行比较的，是动态规划典例。
-
状态设计
f(x)表示以a[x]结尾的LIS长度，那么LIS=max{f(x)}
-
状态转移方程
考虑比x小的每一个p，如果a[x]>a[p]，那么f(x)=f(p)+1,所以f(x)=max{f(p)} + 1，其中p<x且a[p]<a[x]
如果找不到比x小的p，那么f(x)=1，也就是以它结尾的LIS就是他自己，长度为1
可以得出f[0]=1,f[1]=1,f[2]=2,f[3]=3,f[4]=4,f[5]=3
代码实现
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
|
package test;
import java.util.*;
/**
* 给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）
* 示例：
* 输入：[1,2,8,6,4]
* 返回值：[1,2,4]
* 说明：其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）
*/
public class LIS {
/**
* 最长上升序列，索引x，以s[x]结尾的最长上升序列
*/
private List<Integer>[] lis;
/**
* 原始序列
*/
private int[] s;
/**
* 最长子序列长度，索引x，以s[x]结尾的LIS长度
*/
private int[] f;
public LIS(int[] arr) {
s = arr;
f = new int[arr.length];
lis = new ArrayList[s.length];
// 初始化，假设f[i]长度1也即以f[i]结尾的LIS仅包括自己
Arrays.fill(f, 1);
for (int i = 0; i < arr.length; i++) {
lis[i] = new ArrayList<>();
lis[i].add(s[i]); // 假设以s[i]结尾的LIS仅包含自己
}
}
private void processLIS() {
// 最长子序列长度，索引i，以s[i]结尾的LIS长度
for (int i = 0; i < s.length; i++) {
// 如果存在j < i 并且 s[j] < i 那么f[i] = max{1, f[j]+1}
for (int j = 0; j < i; j++) {
// 切记使用f[i] <= f[j] + 1，因为可能存在诸如2568，1348这种情况，长度一样时需要按字典序过滤
if (s[j] < s[i] && f[i] <= f[j] + 1) { // 有以f[i]结尾，从f[j]路线抵达的LIS替换原先的LIS
// 处理f[i]
f[i] = f[j] + 1;
// 防止出现以同一个元素结尾的LIS有多个，例如 139和259 都是以9结尾的长度为3的LIS，为保证以arr[i]结尾的LIS只有一个，在此处直接用字典排序过滤
List<Integer> tmp = new ArrayList<>();
tmp.addAll(lis[j]);
tmp.add(s[i]);
if(tmp.size() > lis[i].size()) {
lis[i] = tmp;
} else if(tmp.size() == lis[i].size()) {
lis[i] = filterByOrder(tmp, lis[i]);
} else {
throw new RuntimeException("error processLIS 1");
}
}
}
}
}
public int getLISMaxLength() {
processLIS();
int max = Integer.MIN_VALUE;
for (int i = 0; i < f.length; i++) {
max = Math.max(max, f[i]);
}
return max;
}
public List<Integer> getLIS() {
List<Integer> res = null;
int maxLength = getLISMaxLength();
for (int i = 0; i < f.length; i++) {
if (maxLength == f[i]) {
if (res == null) {
res = lis[i];
} else {
// 说明出现不止一个LIS，需要按字典序过滤
res = filterByOrder(res, lis[i]);
}
}
}
return res;
}
/**
* 返回字典序较小的LIS
* @param lis1
* @param lis2
* @return
*/
private List<Integer> filterByOrder(List<Integer> lis1, List<Integer> lis2) {
if(lis1.size() != lis2.size()) {
throw new RuntimeException("error filterByOrder");
}
for(int i = 0; i < lis1.size(); i++) {
if(lis1.get(i) == lis2.get(i)) {
continue;
} else if(lis1.get(i) > lis2.get(i)) {
return lis2;
} else {
return lis1;
}
}
throw new RuntimeException("error filterByOrder,no result");
}
public static void main(String[] args) {
// 25689 13489
int arr[] = {2,1,5,3,6,4,8,9,7};
LIS lis = new LIS(arr);
System.out.println(lis.getLIS());
}
}
// 运行结果
[1, 2, 4]
|
