开发者社区> 流楚丶格念> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

R7-1 最长上升子序列 (15 分)

简介: R7-1 最长上升子序列 (15 分)
+关注继续查看

R7-1 最长上升子序列 (15 分)


给定一个序列,求它的一个递增子序列,使它的元素个数尽量多,求该序列的最长上升子序列中元素个数。例如序列1,6,2,5,4,7的最长上升子序列是1,2,5,7或1,2,4,7,则其最长上升子序列中的元素个数为4。


输入格式:


第一行中输入序列的个数(不超过20),第二行中输入每个元素,以空格隔开。


输出格式:


输出该序列中最长上升子序列中的元素个数。


输入样例:


6
1 6 2 5 4 7


输出样例:


4


代码


#include <iostream>
#include <stack>
using namespace std;

int n;
int a[20];
stack<int> st;
int maxlen = 0;

// 深度优先搜索
void dfs(int i)
{
    // 如果按照当前数据线路查到头了,比较当前数据线路的长度与之前所取数据线路,记录最大值
    // 每次搜都是要判断一下这个的
    if (i == n)
    {
        if (st.size() > maxlen)
            maxlen = st.size();
        return;
    }
    // 如果下一个搜索的数组元素大于栈顶  那么把他弄到栈里
    if (st.empty() || a[i] > st.top()) {
        st.push(a[i]);
        // 如果当前元素能行  那么顺着当前元素继续搜索下一条元素
        dfs(i + 1);

        // 上面执行的过程可能很长,能执行到这一步说明  线路已经回退回来了,那么把这个元素弄出去  继续搜索下一个
        st.pop();
    }

    dfs(i + 1);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    // 从第0层开始搜索
    dfs(0);
    cout << maxlen << endl;

    return 0;
}

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
7-21 求特殊方程的正整数解 (15 分)
本题要求对任意给定的正整数N,求方程X2+Y2=N的全部正整数解。
23 0
FastAPI(1)- 简单介绍
FastAPI(1)- 简单介绍
37 0
DevSecOps邂逅云原生:云原生时代下的持续安全
安全可能对于很多业务开发与运维来说,是“麻烦”与“被动”。 相比传统,云原生架构具备了一系列特性,使安全能够更低摩擦地内生于企业流程之中,内生于DevOps之中。 希望与大家讨论的是,在云原生架构下,在持续加速的业务迭代和CI/CD中,如何实践持续安全(Continous Security)。
86 0
文言文不能编程乎?中国大四小哥哥曰:非也
程序员何苦为难程序员?有人开发了一种“文言文编程语言”,用文言文写的编程语言,密切遵循文言文语法和中国古典文学的基调,被评价过于硬核。
46 0
【字符串处理算法】最长连续字符及其出现次数的算法设计及C代码实现
一、需求描述 输入一个字符串,编写程序找出这个字符串中的最长连续字符,并求出其连续出现的次数。 例如,“123444445”中的最长连续字符是4,其连续出现的次数为5;“abcddef”中的最长连续字符是d,其连续出现的次数为2;“ab”中的最长连续字符是a,其连续出现的次数为1。
996 0
LINUX ubuntu 12.04 svn 1.6.7 苦逼的装了一个下午啊!! 绝对详细!正确!不吭爹!!
客户端使用 SVN://....................访问。 一、安装SVN 服务器 这个简单,只要sudo apt-get install subversion一下就好了。
992 0
+关注
流楚丶格念
csdn平台优质创作者,51cto TOP博主,360图书馆科技博主,燕山大学目前大三在读,日拱一卒,功不唐捐,加油!!!
1010
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载