把输入序列看成波, 所有元素都在区间[a,a+L]内，子序列的频率<=主序列的频率(震荡次数/L)

证明: 已存在某序列seq[n],n>=2, 在任意位置加入第n+1个元素k，设k左右元素分别为l,r且l<=r

若(l<=k<=r || k<l&&l是波谷 || k>r&&r是波峰)则新序列频率不变，其他任意情况都会导致新序列频率增加

刚开始看题目第一反应就是dp，然后灵机一动直接求主序列交替次数，O(n),然后通过了

但是看网上还有其他人全都是用dp，O(n^2)。

是我还有什么情况没考虑到吗？子序列的交替次数有可能>主序列的吗？

#include <stdio.h>
int main(){
	int n;
	while(scanf("%d",&n)!=EOF){
		int cur,k,num=1; bool flag;
		if(n>1){ //跳过开头重复部分并确定初始上还是下 
			scanf("%d",&k); n--;
			while(n--){
				scanf("%d",&cur);
				if(cur==k)continue;
				flag = (cur>k);
				num=2; k=cur;
				break;
			}
		}
		if(num<2){
			while(n--) scanf("%d",&cur);
			printf("1\n");
			continue;
		}
		while(n--){
			scanf("%d",&cur);
			if(cur==k|| (flag^(cur<k))){
				k=cur; continue;
			}
			num++; k=cur;
			flag=!flag;
		}
		printf("%d\n",num);
	}
	return 0;	
}