题目链接

摆动序列

题目描述

image.png

实现代码

动态规划思想：定义两个数组：up[i] 和 down[i]：

  1. up[i]：表示前i个元素而言的最后两个元素为递增的最长摆动序列长度
  2. down[i]：表示前i个元素而言的最后两个元素为递减的最长摆动序列长度

nums[i+1] > nums[i]时更新方式：

up[i+1] = max(up[i], down[i] + 1) down[i+1] = down[i]

nums[i+1] < nums[i]时更新方式：

down[i+1] = max(down[i], up[i] + 1) up[i+1] = up[i]

nums[i+1] == nums[i]时更新方式：

up[i+1] = up[i] down[i+1] = down[i]

最终的结果为：

max(up[n-1], down[n-1])

实现代码：

  1. class Solution {
  2.     public int wiggleMaxLength(int[] nums) {
  3.         int n = nums.length;
  4.         if (n < 2) {
  5.             return n;
  6.         }
  7.         int[] up = new int[n];
  8.         int[] down = new int[n];
  9.         up[0] = down[0] = 1;
  10.         for (int i = 1; i < n; i++) {
  11.             if (nums[i] > nums[i - 1]) {
  12.                 up[i] = Math.max(up[i - 1], down[i - 1] + 1);
  13.                 down[i] = down[i - 1];
  14.             } else if (nums[i] < nums[i - 1]) {
  15.                 up[i] = up[i - 1];
  16.                 down[i] = Math.max(up[i - 1] + 1, down[i - 1]);
  17.             } else {
  18.                 up[i] = up[i - 1];
  19.                 down[i] = down[i - 1];
  20.             }
  21.         }
  22.         return Math.max(up[n - 1], down[n - 1]);
  23.     }
  24. }