[数据结构与算法]蓝桥杯零基础冲过赛-第14天

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

例如， [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][2],其中dp[i][0]代表正数差，dp[i][1]代表负数差。那么再来看题中（交替）这个词，交替意思就是如果nums[i]和前一个数造成正数差，那么nums[i - 1]nums[i]和前一个数就要是造成负数差。
解题：
状态定义：
dp[i][2],dp[i][0]代表到i位置时为正数差的最长子序列，dp[i][1]代表到i位置时为负数差的最长子序列
状态转移：
dp[i][0] = dp[i][1] + 1
dp[i][1] = dp[i][0] + 1
边界条件：
dp[0][0] = 1, dp[0][1] = 1;
编码：

int wiggleMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int> > dp(n, vector<int>(2));
        dp[0][0] = 1;
        dp[0][1] = 1;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                dp[i][0] = dp[i - 1][1] + 1;
                dp[i][1] = dp[i - 1][1];
            } else if (nums[i] > nums[i - 1]){
                dp[i][1] = dp[i - 1][0] + 1;
                dp[i][0] = dp[i - 1][0];
            } else {//可能相等，相等就都可以看成没有这个数
                dp[i][0] = dp[i - 1][0];
                dp[i][1] = dp[i - 1][1];
            }
        }
        return max(dp[n - 1][0], dp[n - 1][1]);
    }