最长上升子序列 题目描述

这是一个简单的动规板子题。

创新互联专注于企业全网整合营销推广、网站重做改版、岢岚网站定制设计、自适应品牌网站建设、H5建站、成都商城网站开发、集团公司官网建设、外贸网站制作、高端网站制作、响应式网页设计等建站业务，价格优惠性价比高，为岢岚等各大城市提供网站开发制作服务。

给出一个由 n ( n ≤ 5000 ) n(n\le 5000) n(n≤5000) 个不超过 1 0 6 10^6 106 的正整数组成的序列。请输出这个序列的最长上升子序列的长度。

最长上升子序列是指，从原序列中按顺序取出一些数字排在一起，这些数字是逐渐增大的。

输入格式

第一行，一个整数 n n n，表示序列长度。

第二行有 n n n 个整数，表示这个序列。

输出格式

一个整数表示答案。

样例 #1 样例输入 #1

6
1 2 4 1 3 4

样例输出 #1

4

提示

分别取出 1 1 1、 2 2 2、 3 3 3、 4 4 4 即可。

思路： 用dp[i]表示序列中第i个元素处的最长上升子序列，那么如果想知道dp[i]的值，则需要找到第i个元素之前的最长上升子序列且此子序列的大元素不能比当前元素大。如果第i个元素前所有的子序列中元素都比它自身大，则说明此时的元素不能与之前的元素构成上升子序列，那么此时dp[i]的值就为1

代码：

#includeusing namespace std;
int a[5000], ans[5000], n;
int main(){cin >>n;
    for(int i = 0; i< n; i++){cin >>a[i];
    }
    ans[0] = 1;
    for(int i = 1; i< n; i++){int maxx = 0;
        for(int j = 0; j< i; j++){if(a[j]< a[i]) maxx = max(maxx, ans[j]);
        }
        ans[i] = maxx + 1;
    }
    sort(ans, ans + n);
    cout<< ans[n - 1];
    return 0;
}

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧

网页名称：【C++】洛谷B3637最长上升子序列-创新互联
新闻来源：http://myzitong.com/article/ccsiee.html