c - 最长递增子序列

Question

任务是找到给定整数数组中最长子序列的长度，使得子序列的所有元素都按升序排序。例如，{15,27,14,38,26,55,46,65,85}的LIS长度为6，最长递增子序列为{15,27,38,55,65,85}。

下面是我写的代码。我不确定我的逻辑是否正确，但代码无法正常运行。如果我尝试输入以下测试用例

91527 号14

程序在 14 之后停止读取值并给出输出 2。它应该读取 9 个值，但代码只读取 3 个值。我已经多次检查我的代码，但不幸的是，我无法发现错误。

#include<stdio.h>
int main()
{
    int N,max_val,i,j,k,l=1;
    int a[100000], track[100000];
    track[0]=0;
    max_val=1;
    scanf("%d",&N);
    for(i=0;i<N;++i)
    {
        printf("x");
        scanf(" %d",&a[i]);
        if(i!=0)
        {
            for(j=0;j<l;++j)
            {
                if(a[i]>a[track[j]])
                {
                    max_val++;
                    track[0]=i;
                    l=1;
                    break;
                }
                else
                {
                    track[l]=i;
                    l++;
                }
            }
        }
    }
    printf("%d",max_val);
    return 0;
}

感谢帮助。谢谢!

Answer 1

噢，好复杂。这里有未定义的行为，它的表达方式很有启发性。一般问题是

            if(a[i]>a[track[j]])  // <-- when i == 2, this first is false with
            {                     //     your input
                max_val++;
                track[0]=i;
                l=1;
                break;
            }
            else
            {
                track[l]=i;       // <-- and you end up here, where you write 
                l++;              //     into track[l] and increase l.
            }

增加l后，返回循环

for(j=0;j<l;++j)

这里j增加了，但是由于l也增加了，所以条件永远不会(除非不是真的，见下文)为假，并且循环继续。从此时起，情况

a[i]>a[track[j]]

始终为 false，因为您不断比较相同的两个数字，因此 l 每回合都会递增，并且这种情况会不断发生。

这种情况一直持续到track充满了两个(因为i仍然是2)。事实上，它会在 track 满后继续，写入内存中 track 后面的任何内容。这是什么，C语言标准中没有定义；对我来说，这恰好是第一个 a，然后是 N、max_val 等等(按照声明的顺序发现)我鼓励您研究一下工具)。 YMMV。所以，对我来说，a也被填充，然后N被2覆盖，max_val等是同样被2覆盖，然后l被2覆盖，然后循环结束。然后你回到

for(i=0;i<N;++i)

...现在 N 是 2，i 刚刚增加到 3。然后循环结束，然后程序结束。

也许不用说，这不是您可以依赖的行为。编译器不必按此顺序排列堆栈变量，优化编译器甚至可以生成不在内存中(或根本不保存)某些变量的代码。但这就是发生的事情。