洛谷1970 花匠
简要题意
给定一个序列，求最长波浪子序列。
波浪序列是指一个大一个小这样循环或一个小一个大这样循环。
简要题解
算法1：DP+线段树优化
设$up[i]$表示到$i$结尾，这一个数比上一个数大的最长长度。
设$down[i]$表示到$i$结尾，这一个数比上一个数小的最长长度。
可以很显然的发现$O(n^2)$的状态转移方程（略）
然后用线段树优化一发，复杂度变为$O(n log 1000000)$
代码略。
算法2：贪心
XJB乱贪心。
首先第一个一定选。
接着第二个只要和第一个不一样就选。
接下来每一个：如果和前一个方向不一样就选，否则用它替代前一个（这样更容易找到方向不一样的。）
就行了。
没错就这么简单，$O(n)$。
代码同样略。（虽然我写了）