最长的子序列

任务是在给定的整数数组中查找最长子序列的长度，以便子序列的所有元素按升序排序。例如，{15,27,14,38,26,55,46,65,85}的LIS长度是6，最长的子序列是{15,27,38,55,65,85}。最长的子序列

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

程序停止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; 
}

帮助表示赞赏。谢谢！

来源

2014-12-06 Pranav Arora

@ Rizier123你英语吗？ – 2014-12-06 15:12:28

http://stackoverflow.com/q/20314420/971127 – BLUEPIXY 2014-12-06 15:25:23

@BLUEPIXY：我不是在寻找解决方案，我更感兴趣的是知道我的代码有什么问题。谢谢！ – 2014-12-06 15:36:10

哦，很好地令人费解。你在这里有未定义的行为，它表达的方式本身是有启发性的。普遍的问题是增加

  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也增加了，条件是从来没有（除了不是真的，见下）false，循环继续。从这以后，病情

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

这一点始终是假的，因为你保持比较相同的两个号码，所以l递增动不动，而这只是不断发生。

这一直持续到track满了两个（因为i仍然是2）。事实上，它在track已满后写入，写入发生在存储器中的track后面的任何情况。这是什么在C语言标准中没有定义;对我来说，这恰好是第一个a，然后N，max_val等按声明的顺序（发现调试器，我鼓励你看看一个工具）。因人而异。因此，对我而言，a也被填满，然后N被2覆盖，max_val等也被2覆盖，然后l被覆盖2，然后才循环结束。然后你回去

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

...现在在哪里N是2和i只是递增到3。然后循环结束，然后程序结束。也许不用说，这不是你可以依赖的行为。编译器不需要按照这个顺序排列堆栈变量，优化编译器甚至可以生成没有在内存中保存某些变量的代码（或者根本不存在）。但那就是发生了什么事。

来源

2014-12-06 15:37:04 Wintermute

最长的子序列

回答

相关问题