LeetCode: Wiggle Subsequence Solution

1/**
2 * @param {number[]} nums
3 * @return {number}
4 */
5// greedy
6var wiggleMaxLength = function (nums) {
7  const N = nums.length
8  let res = 1
9  let pos = {
10    peak: false,
11    valley: false,
12  }
13  for (let i = 1; i < N; i++) {
14    if (nums[i] > nums[i - 1] && !pos.peak) {
15      pos.valley = false
16      pos.peak = true
17      res += 1
18    }
19    if (nums[i] < nums[i - 1] && !pos.valley) {
20      pos.valley = true
21      pos.peak = false
22      res += 1
23    }
24  }
25  return res
26}
27
28// dynamic programming
29var wiggleMaxLength = function (nums) {
30  const N = nums.length
31  const up = Array(N).fill()
32  const down = Array(N).fill()
33  up[0] = 1
34  down[0] = 1
35  for (let i = 1; i < N; i++) {
36    if (nums[i] > nums[i - 1]) {
37      up[i] = down[i - 1] + 1
38      down[i] = down[i - 1]
39    } else if (nums[i] < nums[i - 1]) {
40      up[i] = up[i - 1]
41      down[i] = up[i - 1] + 1
42    } else {
43      up[i] = up[i - 1]
44      down[i] = down[i - 1]
45    }
46  }
47  return Math.max(up[N - 1], down[N - 1])
48}