05 August 2008
给定一个整数数组 nums，返回最长递增子序列的数量。请注意，序列必须严格递增
跟300题比较，这个题是返回共有多少个最长的子序列。
LIS的解法
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
class Solution {
public int findNumberOfLIS(int[] nums) {
int len = nums.length;
int[] f = new int[len], g = new int[len];
int max = 1;
for (int i = 0; i < len; i++) {
f[i] = g[i] = 1;
for (int j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
if (f[i] < f[j] + 1) {
f[i] = f[j] + 1;
g[i] = g[j];
} else if (f[i] == f[j] + 1) {
g[i] += g[j];
}
}
}
max = Math.max(max, f[i]);
}
int result = 0;
for (int i = 0; i < len; i++) {
if (f[i] == max) {
result += g[i];
}
}
return result;
}
}
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
class Solution {
int n;
int[][] tr = new int[2010][2];
int lowbit(int x) {
return x & -x;
}
int[] query(int x) {
int len = 0, cnt = 0;
for (int i = x; i > 0; i -= lowbit(i)) {
if (len == tr[i][0]) {
cnt += tr[i][1];
} else if (len < tr[i][0]) {
len = tr[i][0];
cnt = tr[i][1];
}
}
return new int[]{len, cnt};
}
void add(int x, int[] info) {
for (int i = x; i <= n; i += lowbit(i)) {
int len = tr[i][0], cnt = tr[i][1];
if (len == info[0]) {
cnt += info[1];
} else if (len < info[0]) {
len = info[0];
cnt = info[1];
}
tr[i][0] = len;
tr[i][1] = cnt;
}
}
public int findNumberOfLIS(int[] nums) {
n = nums.length;
// 离散化
int[] tmp = nums.clone();
Arrays.sort(tmp);
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0, idx = 1; i < n; i++) {
if (!map.containsKey(tmp[i])) map.put(tmp[i], idx++);
}
// 树状数组维护 (len, cnt) 信息
for (int i = 0; i < n; i++) {
int x = map.get(nums[i]);
int[] info = query(x - 1);
int len = info[0], cnt = info[1];
add(x, new int[]{len + 1, Math.max(cnt, 1)});
}
int[] ans = query(n);
return ans[1];
}
}