欢迎访问==> 【考研OR保研】机试题
题目描述
一个整数序列的子序列是指从给定序列中随意地(不一定连续)去掉若干个整数(可能一个也不去掉)后所形成的整数序列。
对于一个整数序列 $x_1,x_2,…,x_n$,如果满足下列两个条件之一:
- $\\forall i \\in \[1,n-1\]$,当 $i \\% 2 == 1$ 时,$x_i-x_{i+1}$ 为正,当 $i \\% 2 == 0$ 时,$x_i-x_{i+1}$ 为负。
- $\\forall i \\in \[1,n-1\]$,当 $i \\% 2 == 1$ 时,$x_i-x_{i+1}$ 为负,当 $i \\% 2 == 0$ 时,$x_i-x_{i+1}$ 为正。
那么,我们就称这个整数序列为 ZigZag 序列。
换句话说,ZigZag 序列就是一个序列内元素在增大和减小之间不断切换的序列。
例如 $1,7,4,9,2,5$ 就是一个 ZigZag 序列。
现在,给定一个长度为 $n$ 的整数序列,请你求出它的最长 ZigZag 子序列的长度。
输入格式
第一行包含整数 $n$。
第二行包含 $n$ 个整数。
输出格式
输出一个整数,表示最长 ZigZag 子序列的长度。
数据范围
$1 \\le n \\le 50$,
序列内元素取值范围 $\[1,1000\]$。
输入样例:
6
1 7 4 9 2 5
输出样例:
6
C++ 代码
#include <bits/stdc++.h>
using namespace std;
const int N = 55, INF = 0x3f3f3f3f;
//f[i]表示以第i个数字结尾并且是前一个数字上升得到的a[i]
//g[i]表示以第i个数字结尾并且是前一个数字下降得到的a[i]
//集合划分:【只有一个a[i]】【其他:倒数第二个元素是第j个数字并且需要是下降得到a[j]:g[j] + 1】
//状态计算:f[i] = max(f[i], g[j] + 1);
int f[N], g[N];
int n, a[N], res = -INF;
int main()
{
cin >> n;
for(int i = 1; i <= n; i ++) cin >> a[i];
for(int i = 1; i <= n; i ++)
{
f[i] = g[i] = 1;
for(int j = 1; j < i; j ++)
{
if(a[j] > a[i]) f[i] = max(f[i], g[j] + 1);
if(a[j] < a[i]) g[i] = max(g[i], f[j] + 1);
}
res = max(res, max(f[i], g[i]));
}
cout << res << endl;
return 0;
}
这不是$O(n^2)$吗,算暴力吧
注释里解释的f,g含义和实际代码里的f,g含义反了。如果代码不变,
对于语句:if(a[j] > a[i]) f[i] = max(f[i], g[j] + 1);,
这里的f[i]记录的应该是以a[i]结尾,且由前一个数字下降得到的子序列最大长度