C 中查找列表的最长递增子序列

Question

我在尝试查找构成给定列表的最长递增子序列的元素时遇到问题。

我有算法来查找列表中给定项目的值，并且我了解它使用的方法，我只是不知道要添加什么以及在哪里添加它，以便我拥有组成 LIS 的数字

这是我现在正在做的事情：

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是一个存储部分 LIS 的数组，但在某些时候它会发生变化，因为可能存在不同的解决方案。N是元素数组。

我怎样才能从这里找到 的最长递增子序列N？

Answer 1

您可以使用两个附加数组来查找 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中的元素相比，A[2] 或 4 更有可能是 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