题目

LeetCode.376.摆动序列（中等）

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为摆动序列。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

例如， [1, 7, 4, 9, 2, 5] 是一个摆动序列，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。

相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。
子序列可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为摆动序列的最长子序列的长度。

题解

最值问题考虑动态规划，先划分子问题。

从某个摆动序列最后一个元素开始倒推，得到这个摆动序列有两个情况：

前面的子摆动序列末尾两个元素是递减的，子摆动序列末尾元素和新的数字是递增的。
前面的子摆动序列末尾两个元素是递增的，子摆动序列末尾元素和新的数字是递减的。

子摆动序列怎么得来的，也是同样的递归划分。

这里有两个状态变化，一个是元素位置，一个是末尾差值。

设dp[i][k]表示数组中第0个到第i元素之间最长摆动序列长度；
k表示nums[i]和前面元素是递增或递减的情况；
k == 0 时，表示递减；
k == 1 时，表示递增。

考虑之前相反的情况，如果：

前面的子摆动序列末尾两个元素是递减的，子摆动序列末尾元素和新的数字是递减的，摆动序列长度不会增加；同时新数字作为序列末尾元素，因为之后更有可能形成递增，也就更有可能得到更长的摆动序列。
前面的子摆动序列末尾两个元素是递增的，子摆动序列末尾元素和新的数字是递增的，摆动序列长度不会增加；同时新数字作为序列末尾元素，因为之后更有可能形成递减，也就更有可能得到更长的摆动序列。

状态转移方程

nums[i] < nums[i - 1]，递减：
dp[i][0] = maxOf(dp[i][0], dp[i - 1][1] + 1)
nums[i] > nums[i - 1]，递增：
dp[i][1] = maxOf(dp[i][1], dp[i - 1][0] + 1)
nums[i] == nums[i - 1]，持平：
dp[i][0] = dp[i - 1][0]
dp[i][1] = dp[i - 1][1]

边界处理
最一开始只有一个元素，没有形成递增或递减，所以摆动序列长度为0。
dp[0][0] = 0
dp[0][1] = 0

最后取值
取dp[n - 1][0]和dp[n - 1][1]中较大的。
最后结果还要加1，因为我们是在发生新的摆动的时候才给序列增加长度的，遍历到最后时没有新的摆动了，但是目前的摆动没有算进长度。

class Solution {
    fun wiggleMaxLength(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        val dp = Array(n) { IntArray(2) { 0 } }
        for (i in 1 until n) {
            if (nums[i] < nums[i - 1]) {
                dp[i][0] = maxOf(dp[i - 1][0], dp[i - 1][1] + 1)
            } else if (nums[i] > nums[i - 1]) {
                dp[i][1] = maxOf(dp[i - 1][1], dp[i - 1][0] + 1)
            } else {
                dp[i][0] = dp[i - 1][0]
                dp[i][1] = dp[i - 1][1]
            }
        }
        return maxOf(dp[n - 1][0], dp[n - 1][1]) + 1
    }
}

空间优化
dp[i]只与dp[i - 1]有关，可以用变量记录状态，不用数组。

用up记录末尾递增的摆动序列的最长长度。
用down记录末尾递减的摆动序列的最长长度。

class Solution {
    fun wiggleMaxLength(nums: IntArray): Int {
        val n = nums.size
        if (n == 0) return 0
        var up = 0
        var down = 0 
        for (i in 1 until n) {
            if (nums[i] < nums[i - 1]) {
                down = maxOf(down, up + 1)
            } else if (nums[i] > nums[i - 1]) {
                up = maxOf(up, down + 1)
            }
        }
        return maxOf(up, down) + 1
    }
}