题意：
求给定数列中含有的波动子序列长度的最大值。（如2 3 2 3即为波动数列，注意不一定连续）
这题可以乱搞，也可以贪心，也可以DP。
我这里用的是DP的方法。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<cmath>
#include<cstdlib>
#define ll long long
#define maxn 100010
#define inf 1000000000
#define linf (1LL<<50)
using namespace std;
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x*=10;x+=ch-'0';ch=getchar();}
return x*f;
}
inline void read(char *s,int &ts)
{
char x=getchar();
while(!(x>='a'&&x<='z'))x=getchar();
while(x>='a'&&x<='z')s[++ts]=x,x=getchar();
}
int n,ans=0;
int a[maxn];
int f[4001][4001];
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int last=0;
for(int j=0;j<i;j++)
{
f[i][j]=f[j][last]+1;
if(a[i]==a[j]) last=j;
ans=max(f[i][j],ans);
}
}
printf("%d\n",ans);
return 0;
}
评论 (0)
