我在尝试查找构成给定列表的最长递增子序列的元素时遇到问题。
我有找到列表中给定项目值的算法，我了解它使用的方法，我只是不知道要添加什么以及在哪里添加它，以便我拥有组成 L.I.S. 的数字。
这是我现在正在做的事情:
for (A[0] = N[0], i=lis=1; i<n; i++) {
int *l = lower_bound(A, A+lis, N[i]);
lis = max(lis, (l-A)+1);
*l = N[i];
}
A 是一个存储部分 L.I.S. 的数组，但在某些时候它会发生变化，因为可能有不同的解决方案。 N 是元素数组。我怎样才能从这里找到
N 的最长递增子序列？ 最佳答案
您可以使用两个额外的数组来查找 LIS。例如，如果你的源代码放在一个数组中 A
1 8 4 12 6 6 1
我们有一个数组 B 来存储 A 的元素，这些元素更有可能是 LIS 的元素。更准确地说， B 将在 i 位置作为 LIS 进行维护。
加上一个数组 idx 来记录位置。
我们从 A[0] 开始，将 A[0] 放在 B[0] 处。由于 A[0] 附加在 B 中的位置 0，因此 idx[0] = 0。
[0] 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
B | (1)
idx | 0
那么对于位置1，由于 B 中的元素小于A[1]，所以将A[1]附加到B。idx[1]记录了 B 中的位置为1。
0 [1] 2 3 4 5 6
A | 1 8 4 12 6 6 1
B | 1 (8)
idx | 0 1
对于位置 2，A[2] 或 4 与 B 中的元素相比更可能是 LIS 的元素，以便将 B 保持为 LIS。所以找到 B 中最小的不小于4的元素并替换，即8。idx[2]设置为 B 中替换8的位置。我认为您可以使用搜索算法来找到这样的元素。
0 1 [2] 3 4 5 6
A | 1 8 4 12 6 6 1
B | 1 (4)
idx | 0 1 1
所以继续这种方式，我们逐渐设置 idx 。
position 3
0 1 2 [3] 4 5 6
A | 1 8 4 12 6 6 1
B | 1 4 (12)
idx | 0 1 1 2
position 4
0 1 2 3 [4] 5 6
A | 1 8 4 12 6 6 1
B | 1 4 (6)
idx | 0 1 1 2 2
position 5
0 1 2 3 4 [5] 6
A | 1 8 4 12 6 6 1
B | 1 4 (6)
idx | 0 1 1 2 2 2
position 6
0 1 2 3 4 5 [6]
A | 1 8 4 12 6 6 1
B | (1) 4 6
idx | 0 1 1 2 2 2 0
我们有 idx 记录的位置，现在我们向后扫描 idx 并找出 LIS。
0 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
idx | 0 1 1 2 2 (2) 0 | 6
0 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
idx | 0 1 (1) 2 2 2 0 | 4 6
0 1 2 3 4 5 6
A | 1 8 4 12 6 6 1
idx | (0) 1 1 2 2 2 0 | 1 4 6
因此，输出 LIS 是 {1, 4, 6}
代码和 A = {1, 8, 4, 12, 6, 6, 1} 作为源
#include <stdio.h>
#include <stdlib.h>
#define INT_INF 10000
int search_replace(int *lis, int left, int right, int key) {
int mid;
for (mid = (left+right)/2; left <= right; mid = (left+right)/2) {
if (lis[mid] > key) {
right = mid - 1;
} else if (lis[mid] == key) {
return mid;
} else if (mid+1 <= right && lis[mid+1] >= key) {
lis[mid+1] = key;
return mid+1;
} else {
left = mid + 1;
}
}
if (mid == left) {
lis[mid] = key;
return mid;
}
lis[mid+1] = key;
return mid+1;
}
int main(void) {
int i, tmp, size = 7, lis_length = -1;
int *answer;
int A[7] = {1,8,4,12,6,6,1},
LIS[7],
index[7] = {0};
LIS[0] = A[0];
for (i = 1; i < size; ++i) {
LIS[i] = INT_INF;
}
for (i = 1; i < size; ++i) {
index[i] = search_replace(LIS, 0, i, A[i]);
if (lis_length < index[i]) {
lis_length = index[i];
}
}
answer = (int*) malloc((lis_length+1) * sizeof(int));
for (i = size-1, tmp = lis_length; i >= 0; --i) {
if (index[i] == tmp) {
answer[tmp] = A[i];
--tmp;
}
}
printf("LIS: ");
for (i = 0; i < lis_length+1; ++i) {
printf("%d ", answer[i]);
}
printf("\n");
return 0;
}
和代码的输出
LIS: 1 4 6
关于c - 在C中查找列表的最长递增子序列，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12346348/