您好,欢迎来到华佗小知识。
搜索
您的当前位置:首页最长上升子序列【LIS】<动态规划>

最长上升子序列【LIS】<动态规划>

来源:华佗小知识

【题目描述】

给定N个数,求这N个数的最长上升子序列的长度

【样例输入】

7

2 5 3 4 1 7 6

【样例输出】

4

代码:

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define Max 1010
//最长上升序列
int a[Max];
int maxlen[Max];
int main()
{

    int N;
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> a[i];
        maxlen[i]=1;
    }
    for (int i = 2; i <= N; i++)
        for (int j = 1; j < i; j++)
        {
            if (a[i] > a[j])
            {
                maxlen[i] = max(maxlen[j] + 1, maxlen[i]);
            }
        }
    cout << *max_element(maxlen + 1, maxlen + N + 1);
    return 0;
}

因篇幅问题不能全部显示,请点此查看更多更全内容

Copyright © 2019- huatuo0.cn 版权所有 湘ICP备2023017654号-2

违法及侵权请联系:TEL:199 18 7713 E-MAIL:2724546146@qq.com

本站由北京市万商天勤律师事务所王兴未律师提供法律服务