最长上升子序列c++

这题思路是这样，假设这个序列长度为n，存在数组a中，maxlen[i]表示以第i个数为终点的最长上升子序列的长度，它被初始化为1，因为一开始单个字符的最长上升子序列都是1（它自己），我们先用一个循环i遍历这个序列，i从2（序列的第2个字符）开始一直加1加到n，表示求以第i个数为终点的最长上升子序列的长度，然后同时在这个循环下再来一个循环j，j从1开始加1一直加到i-1为止，表示以第j个数为终点的最长上升子序列。只要出现a[i]>a[j]的情况，maxlen[i]=max(maxlen[i],maxlen[j] 1),首先看maxlen[j] 1,因为a[i]>a[j]了，说明以第j个数为终点的最长上升子序列后面又多了一位比这个最长上升子序列大的，也就是a[i]，这个序列变成以a[i]为终点的了，所以长度要加1，注意j的范围是（1,i-1）,所以以第i个数为终点的最长上升子序列的长度至少是maxlen[j] 1,再跟maxlen[i]比较，因为maxlen[i]通过更新是有可能比maxlen[j] 1大的。

我们用图来表示这个解法，以题目例子的序列来说：

初始时单个字符的最长上升子序列是它本身，为1：

第1次i从2（对应数字7）开始，所以j从1到i-1也就是1 （对应数字1），7>1,我们发现a[i]>a[j]了，所以maxlen[i]=max(maxlen[i],maxlen[j] 1)，maxlen[2]=max(1,1 1),maxlen[2]=2,所以在7下面的1数是1下面的1数再加一笔：

 第2次i从3（对应数字3）开始，所以j从1到i-1也就是1,2（对应数字1,7）,发现3比1大，所以3下面的1数是1下面的1数又加一笔，也就是比谁大，就把谁下面的1的数量拿（覆盖原来的）过来再加1，比7小所以不加：

 接着i到4（对应数字5）了，比j的数字1和3都大，但是比较后3下面的1数最多，所以以它的加1，覆盖到5上，5下面就对应3了，接着i到9以此类推，最后的图是这样：

有几个1就代表了以这个数为终点的最长上升子序列的长度是多少，最后直接求最大输出就行了。 

代码如下：

1.  
   #include<bits/stdc .h>
2.  
   using namespace std;
3.  
   const int maxn = 1010;
4.  
   int a[maxn];
5.  
   int maxlen[maxn]={0};
6.  
   int main()
7.  
   {
8.  
   int n;
9.  
   cin>>n;
10.  
    for(int i=1;i<=n;i )//存入序列，并初始化maxlen[i]
11.  
    {
12.  
    cin>>a[i];
13.  
    maxlen[i]=1;
14.  
    }
15.  
    for(int i=2;i<=n;i )
16.  
    {
17.  
    for(int j=1;j<i;j )
18.  
    {
19.  
    if(a[i]>a[j])
20.  
    maxlen[i]=max(maxlen[i],maxlen[j] 1);
21.  
    }
22.  
    }
23.  
    int maxone=-1;
24.  
    for(int i=1;i<=n;i )//找出maxlen[i]中值最大的
25.  
    {
26.  
    maxone=maxone>maxlen[i]?maxone:maxlen[i];
27.  
    }
28.  
    cout<<maxone<<endl;
29.  
    return 0;
30.  
    }

这篇好文章是转载于：学新通技术网