最长上升子序列
  anLrwkgbyYZS 2023年12月30日 12 0


      最长上升子序列:给你一个数列,你可以从从中选一些数字,要求这些数字是递增的,问你选出的递增数列最大长度。

      思路:开一个数组,如dp[n], n 是这个数列的长度,  dp[i]的意思是以数列中第i个数字结尾的最长上升子序列。

      手动模拟一下: 给你一个数列 a  ={1 ,3 ,4, 2 }  长度为4 , 假设下标从1开始,便于理解。

                              1.  初始dp[5]全部为 1。

                              2.以1结尾的最长子序列为1  即 dp[1]=1(就是它自己)

                              3.以3结尾的最长子序列,枚举他前边的dp,因为a[1] =1 < a[2] = 3 ,  所以dp[2]=max(dp[2],dp[1]+1)=2;   (dp[1]+1  的意思是 以a[1]=1结尾的最长子序列长度加上1(因为a[2]>a[1])  下同)

                              4.以4结尾的子序列,a[1] =1< a[3] = 4 ,所以dp[3]=max(dp[3],dp[1]+1) = 2;

                                                                      a[2] =3 <  a[3]=4, 所以dp[3]=max(dp[3],dp[2]+1) = 3;

                              5.以2结尾的最长子序列, a[1]=1<a[4] =2,,所以dp[4]=max(dp[4],dp[1]+1) =2;

                                                                                a[2]>a[4]  , 这种情况不更新 dp[4]

                                                                                a[3]>a[4]  ,  同样也不更新

参考代码:

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 10000;
int dp[N];//  dp[i]的意思是以数列中第i个数字结尾的最长上升子序列
int a[N];// 存储原数列
int main()
{
    int n;
    scanf("%d",&n); // 输入原数列长度
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&a[i]);  // 输入原数列各个位上的数字,下标从 1 开始
    }

    for(int i=1; i<=n; i++)
        dp[i]=1;     // 初始化

    int maxlen = 1; // 最长子序列
    for(int i=2; i<=n; i++) // 更新以 a[i] 结尾的最长子序列
        for(int j=1; j<i; j++)
        {
            if(a[i]>a[j])
            {
                dp[i] = max(dp[j]+1,dp[i]);

                if(dp[i]>maxlen)
                    maxlen=dp[i]; // 记录最长子序列
            }
        }

    printf("%d\n",maxlen);
    return 0;
}

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

上一篇: 1117 聪明的木匠 下一篇: Milking Time POJ - 3616
  1. 分享:
最后一次编辑于 2023年12月30日 0

暂无评论

anLrwkgbyYZS