大家好，又见面了，我是你们的朋友全栈君。
题目：
输入一个整数n，随后输入n个整数，求这个长度为n的序列中严格递增的子序列的最长长度。
例：
输入：
6
1 4 3 2 6 5
输出：
3
解题思路：
动态规划。将输入的序列存入一个数组v中，另外再定义一个数组a，用以存储以当前数字v[i]结尾时，最长递增子序列的长度是多少。
定义数组时，全部初始化为1，初始状态表示的是最坏的情况，以v[i]结尾的最长递增子序列就是v[i]它本身，长度为1。接着将v[i]逐一与前面的数字v[x]进行比较，x∈[0,i)，若发现v[x]<v[i]，说明v[i]可作为后继元素增加到以v[x]结尾的递增子序列中，则a[i]=v[x]+1，但是在将v[i]逐一与v[x]进行比较的过程中，我们需要找出最大的v[i]，所以将每一次v[i]需要更新的值与它本身的值进行比较，取大的那一个就行了，保持在每一次v[i]与v[x]比较之后，v[i]的值都是最大的。最后，找出数组v中最大值就是结果。
再来看看样例，a[0]~a[5]的初始值都是1，
首先求以v[1]结尾的最长递增子序列长度。v[1]>v[0]，说明4可作为1的后继成为递增序列，以1结尾的递增序列长度a[0]为1(默认值)，则a[1]可以等于a[0]+1，同时a[1]本身也是1，a[0]+1>a[1]，所以最终a[1]=a[0]+1=2；接着求v[2]
结尾的最长递增子序列长度，将v[2]与v[0]进行比较，v[2]>v[0]同时a[0]+1>a[2]，所以a[2]=a[0]+1=2；将v[2]与v[1]进行比较，v[2]<v[1]，则a[2]的值不变，最终a[2]=2；接着求v[3]结尾的最长递增子序列长度，v[3]>v[0]且a[0]+1>a[3]，a[3]=a[0]+1=2；v[3]<v[1]，a[3]值不变为2；v[3]<v[2]，v[3]值不变为2，所以最终a[3]的值为2。后面的v[4]与v[5]依此类推。
首先求以v[1]结尾的最长递增子序列长度。v[1]>v[0]，说明4可作为1的后继成为递增序列，以1结尾的递增序列长度a[0]为1(默认值)，则a[1]可以等于a[0]+1，同时a[1]本身也是1，a[0]+1>a[1]，所以最终a[1]=a[0]+1=2；接着求v[2]
结尾的最长递增子序列长度，将v[2]与v[0]进行比较，v[2]>v[0]同时a[0]+1>a[2]，所以a[2]=a[0]+1=2；将v[2]与v[1]进行比较，v[2]<v[1]，则a[2]的值不变，最终a[2]=2；接着求v[3]结尾的最长递增子序列长度，v[3]>v[0]且a[0]+1>a[3]，a[3]=a[0]+1=2；v[3]<v[1]，a[3]值不变为2；v[3]<v[2]，v[3]值不变为2，所以最终a[3]的值为2。后面的v[4]与v[5]依此类推。
代码：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n;
cin>>n;
vector<int> v(n);
vector<int> a(n,1);
for(int i=0;i<n;i++)
cin>>v[i];
for(int i=1;i<n;i++)
for(int j=0;j<i;j++)
if(v[i]>v[j])
a[i]=max(a[i],a[j]+1);
sort(a.begin(),a.end());
cout<<a[n-1];
return 0;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/136700.html原文链接：https://javaforall.net
