最长不下降序列LICS

diggersun

题目：给定一个序列，求它的一个子序列，保证后面一个数字不小于前面的数字，并且最长。
比如 1 3 5 9 7 8 6 4 2 0 这个序列，1 3 5 7 8 是它的一个子序列，长度为5，后面的数字不小于前面的数字，并且，找不到比它更长的。

diggersun

我上课时候讲的是标准做法，虽然略有一点繁琐，但是清晰，扩展性强，同学们要认真去理解。虽然有的书上或者网上讲的比我的简单，但是，损失了一点扩展性，等熟练之后大家也可以学习网上的做法。
思路：用a数组表示每个数字的值，l数字表示目前最大的长度，f数组表示这个数字的前驱，p数组表示路径。

1. #include<iostream>
   
2. #include<iomanip>
   
3. using namespace std;
   
4. int a[11]= {0,1,7,3,5,9,2,8,6,4,99}; //假设有9个数字分别是1,7,3,5,9,2,8,6,4，第一个位子空着，最后一个是假标记
   
5. int l[11]; //到当前为止的最长不下降序列的长度
   
6. int f[11]; //当前最优决策时的前驱的编号
   
7. int p[11];//输出路径时用的数组
   
8. int i,j;
   
9. int main()
   
10. {
    
11.     for (i=0; i<=10; i++)
    
12.     {
    
13.         l[i]=1;  //至少的长度是1
    
14.         f[i]=-1; //不需要前驱
    
15.     }
    
16. 
    
17.     for(i=2; i<=10; i++) ///枚举当前位置
    
18.         for (j=1; j<i; j++) ///枚举当前位置前面的所有可能
    
19.             if (a[j]<=a[i])  ///不下降
    
20.                 if (l[j]+1>=l[i])        ///最长
    
21.                 {
    
22.                     l[i]=l[j]+1;  ///决策
    
23.                     f[i]=j;       ///记录前驱
    
24.                 }
    
25. 
    
26.     for (i=0; i<=10; i++)
    
27.         cout<<setw(4)<<a[i];
    
28.     cout<<endl;
    
29.     for (i=0; i<=10; i++)
    
30.         cout<<setw(4)<<l[i];
    
31.     cout<<endl;
    
32.     for (i=0; i<=10; i++)
    
33.         cout<<setw(4)<<f[i];
    
34.     cout<<endl;
    
35.     i=0;
    
36.     p[i]=10; ///最后一个绝对是最长的
    
37.     while (f[p[i]]!=-1)  ///还有前驱
    
38.     {
    
39.         i++;
    
40.         p[i]=f[p[i-1]];
    
41.     }
    
42. 
    
43.     for (j=i; j!=-1; j--) cout<<a[p[j]]<<' '; ///输出最后的路径
    
44.     return 0;
    
45. }
    
46. 
    

复制代码

diggersun

上面的做法很直观但是浪费也是很严重的，怎么改进呢

diggersun

diworth定理

SilverMOR

那么然后呢

张笑宇

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,a[10010],d[10010],len;
   
5. int main()
   
6. {
   
7.     cin>>n;
   
8.     for (int i=1; i<=n; i++) cin>>a[i];
   
9.     len=1,d[1]=a[1];
   
10.     for (int i=2; i<=n; i++)
    
11.     {
    
12.         if (a[i]>=d[len])///不下降
    
13.             d[++len]=a[i];
    
14.         else
    
15.         {
    
16.             int l=0,r=len,mid;
    
17.             while (l<r)
    
18.             {
    
19.                 mid=(r-l)/2+l;
    
20.                 if (d[mid]>a[i]) r=mid;
    
21.                 else l=mid+1;
    
22.             }
    
23.             d[l]=a[i];
    
24.         }
    
25.     }
    
26.     cout<<len;
    
27.     return 0;
    
28. }
    

复制代码

黄煦喆

1. #include<iostream>
   
2. using namespace std;
   
3. int a[101],l[101],f[101],n;
   
4. void dfs(int x)
   
5. {
   
6.     if(f[x]!=-1)dfs(f[x]);
   
7.     cout<<a[x]<<' ';
   
8. }
   
9. int main()
   
10. {
    
11.     cin>>n;
    
12.     for(int i=1;i<=n;++i)cin>>a[i],l[i]=1,f[i]=-1;
    
13.     for(int i=1;i<n;i++)
    
14.         for(int j=i+1;j<=n;j++)
    
15.         if(a[j]>=a[i]&&l[j]<l[i]+1)
    
16.         {
    
17.             l[j]=l[i]+1;
    
18.             f[j]=i;
    
19.         }
    
20.     int k=1,t=1,maxa=-1;
    
21.     while(t<=n)
    
22.     {
    
23.         if(l[t]>maxa)maxa=l[t],k=t;
    
24.         t++;
    
25.     }
    
26.     dfs(k);
    
27.     return 0;
    
28. }
    

复制代码

zhwang

1. #include<cstdio>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n;
   
5. int a[10001];
   
6. int f[10001];
   
7. int main()
   
8. {
   
9.         scanf("%d",&n);
   
10.         for(int i=1;i<=n;i++)
    
11.         {
    
12.                 scanf("%d",&a[i]);
    
13.         }
    
14.         f[1]=1;
    
15.         for(int i=1;i<=n;i++)
    
16.         {
    
17.                 for(int j=i-1;j>=1;j--)
    
18.                 {
    
19.                         if(a[j]<=a[i])
    
20.                         {
    
21.                                 f[i]=f[j]+1;
    
22.                                 break;
    
23.                         }
    
24.                 }
    
25.         }
    
26.         int ans=0;
    
27.         for(int i=1;i<=n;i++)
    
28.         {
    
29.                 ans=max(ans,f[i]);
    
30.         }
    
31.         printf("%d",ans);
    
32.         return 0;
    
33. }

复制代码

黄煦喆

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. int n,len,l,r,mid;
   
5. int a[101],b[101];
   
6. int main()
   
7. {
   
8.     cin>>n;
   
9.     for(int i=1;i<=n;i++)cin>>a[i];
   
10.     b[1]=a[1];
    
11.     len=1;
    
12.     for(int i=2;i<=n;i++)
    
13.         if(a[i]>=b[len])b[++len]=a[i];
    
14.         else
    
15.         {
    
16.             int k=upper_bound(b+1,b+len+1,a[i])-b;
    
17.             b[k]=a[i];
    
18.         }
    
19.     cout<<len<<endl;
    
20.     return 0;
    
21. }
    

复制代码