大家好,又见面了,我是你们的朋友全栈君。
首先求以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;
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136700.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...