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]
|