algorithm - 最长递增子序列

Question

对于数字 N，我们将 LIS 数组 定义为

以该数字结尾的数字的最长严格递增子序列。

例如，假设 4 位数字为 1531，则 LIS 数组将为 [1, 2, 2, 1]。

以第一个数字结尾的最长递增子序列是 1(数字 1 本身)，第二个数字是 2 ([1, 5])，第三个数字也是 2 ([1, 3])，第四个数字是1(数字 1 本身)。

Problem Statement

这里我使用的是位掩码算法

for(int i=2;i<=n;i++){
    int x = Lis[i];

    if(x==1){
        for(int j=1;j<(1<<10);j++){
            int last=-1;
            int len=0;
            for(int k=9;k>=0;k--)
                if((j&(1<<k))!=0){ 
                    len++;
                    if(len==1)
                        last=k;
                }

            for(int k=0;k<=last;k++){
                dp[1<<k][i] = (dp[1<<k][i]+ dp[j][i-1])%mod;
            }
        }

        continue;
    }

    for(int j=1;j<(1<<10);j++){
        int last=-1;
        int len=0;
        for(int k=9;k>=0;k--)
            if((j&(1<<k))!=0){ 
                len++;
                if(len==1)
                    last=k;
            }
        if(len+1!=x) continue;

        for(int k=last+1;k<10;k++)
            dp[j|(1<<k)][i] = (dp[j|(1<<k)][i]+ dp[j][i-1])%mod; 
    }
}

但是它不能正常工作？任何人都可以向我解释处理此问题的正确方法吗？

Answer 1

为每个数字存储最长关联序列的长度并遍历序列:

max_len[]
result

for digit in sequence
    max_len[digit] = max(sub_array(max_len, 1, digit - 1)) + 1
    result.append(max_len[digit])

由于 max_len 的长度为 9 或 10，具体取决于输入序列中是否允许使用 0，因此此解决方案的运行时间为 O(n)。 result 包含 LIS 数组。

基本思想是将输入序列中元素 e 的 LIS 递归定义为 e 之前且小于 的任何元素的 LIS >e。因为我们想要最长的序列，所以我们显然选择了具有最长序列的前驱。我们可以将这个值作为以元素e结尾的最长序列记住，以备后用，并将e的LIS长度添加到输出序列中。