EOJ(动态规划）——2083. ZigZag

单测试点时限: 2.0 秒

内存限制: 256 MB

A sequence of numbers is called a zig-zag sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a zig-zag sequence.

For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because its first two differences are positive and the second because its last difference is zero.

输入
Given a sequence of integers, sequence, return the length of the longest subsequence of sequence that is a zig-zag sequence. A subsequence is obtained by deleting some number of elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.

sequence contains between 1 and 50 elements, inclusive.
Each element of sequence is between 1 and 1000, inclusive.
输出
output the length of the longest subsequence of sequence that is a zig-zag sequence.

样例
input
10
1 17 5 10 13 15 10 5 16 8
output
7
input
6
1 7 4 9 2 5
output
6

题目大意：

求最长子串的问题，子串类似上下跳跃的波形，高-低-高-低…

题目解析：

给每个序列的数字都记录两个值，pdp[i]:这个值作为一个波峰最高顺位,ndp[i]:这个值作为一个波谷最高顺位。然后状态转移方程：
pdp[i]={0~i-1中满足A[j]<A[i]的ndp最大值}
ndp[i]={0~i-1中满足A[j]>A[i]的pdp最大值}

具体代码：

#include<iostream>
#include<algorithm>
using namespace std;
#define MAXN 100
int A[MAXN];
int pdp[MAXN];//ndp 指的是这个值作为一个波峰最高顺位 
int ndp[MAXN];//ndp 指的是这个值作为一个波谷最高顺位
int main() {
	int n;
	scanf("%d",&n); 
	for(int i=0;i<n;i++)
		scanf("%d",&A[i]);
	for(int i=0;i<n;i++){
		int pmax=0,nmax=0;
		for(int j=0;j<i;j++){
			if(ndp[j]>pmax&&A[j]<A[i])
				pmax=ndp[j];
			if(pdp[j]>nmax&&A[j]>A[i])
				nmax=pdp[j];
		}
		pdp[i]=pmax+1;
		ndp[i]=nmax+1;
	}
	int res=0;
	for(int i=0;i<n;i++){
		res=max(res,pdp[i]);
		res=max(res,ndp[i]);
	}
	cout<<res<<endl; 
	return 0;
}