锐客网

  1. 首页 > it技术 > >

ACM|最长上升子序列的求法

ACMiostreamnamespace

相信大家已经知道了什么叫最长上升子 序列，在这，我不在描述。给你一串数字，比如：1 7 6 5 8 9 4 10 11
求它的最长上升子序列。
解题思路：
【ACM|最长上升子序列的求法】首先，要求它的最长上升子序列，有n个数，它的上升子序列是以这n个数中任何一个数结尾的，比如上面的，可能是以1,7,6,5,8,9,4,10,11中的每一个结尾的，我们只需要先求从出以每个结尾的上升子序列，然后在再找出这n个子序中最大的，最大的就是最长上升子序列。实现如下：
#include
using namespace std;
int main()
{
int a[1010],b[1010],i,j,n,count; //a[]用来存输入的数据，b[]用来存n个子序列中每个子序列的长度
cin>>n;
for(i=1; i<=n; i++)
cin>>a[i]; // 输入n个数
b[1]=1;
for(i=2; i<=n; i++)
{
count=0; //count用来记录当前从1到j中中最长上升子序列的长度，
for(j=1; j{
if(a[i]>a[j])//因为这个子序列是以j结尾的子序列，所以a[i]<=a[j]的情况自然不满足条件。就不需要考虑了
{
if(countcount=b[j]; //count如果 小于b[j]，就让count等于b[j]，因为count是我们要找的子序列的长度，而且是当前最长的
}
}
b[i]=count+1; //因为此时循环结束后i的值要比j大1。所以b[i]的值要在count的基础上加1
}
count=0;
for(i=1; i<=n; i++)
{
if(countcount=b[i]; //找最长上升子序列
}
cout< }

    推荐阅读


    上一篇：如何在github上下载某个项目的单独某个目录

    下一篇：环境搭建|linux 下 ab 和 websocket-bench 安装