给定一个长度为N的数组，找出一个最长的单调自增子序列
发布时间
阅读量：
阅读量
在牛客网上看到了这么道题
给定一个长度为N的数组，找出一个最长的单调自增子序列（不一定连续，但是顺序不能乱）
例如：给定一个长度为8的数组A{1,3,5,2,4,6,7,8}，则其最长的单调递增子序列为{1,2,4,6,7,8}，长度为6.
结果做了一下午最终发现思路是错的，看了答案豁然明朗了，所以赶紧记录下来。
答题思想就是如果后者比前者大并且前者递增数组的长度+1大于后者递增数组的长度，就说明满足，
感觉描述不清楚，还是直接上代码吧。
#include<iostream>
#include<vector>
using namespace std;
int maxLen(int *a,int n)
{
vector<int> vlen(n,1);
int maxLen=1;
for(int i=1;i<n;++i)
{
for(int j=0;j<i;++j)
{
if(a[i]>a[j]&&vlen[j]+1>vlen[i])
vlen[i]=vlen[j]+1;
}
if(maxLen<vlen[i])
maxLen=vlen[i];
}
return maxLen;
}
int main()
{
int T;
while(cin>>T)
{
while(T)
{
--T;
int n;
cin>>n;
int *a=new int[n];
for(int i=0;i<n;++i)
cin>>a[i];
cout<<maxLen(a,n)<<endl;
delete []a;
}
}
return 0;
}反正就是那个样子，就是慢慢feel吧，太困了，虽然今晚有女排半决赛，但是我实在是太困了，女排加油，我先去睡会
全部评论 (0)
还没有任何评论哟~