1
class Solution {
2
  int n;
3
  int dp[][][];
4

5
  public int wiggleMaxLength(int[] nums) {
6
    n = nums.length;
7
    dp = new int[n][1005][2];
8
    for (int i = 0; i < n; i++) {
9
      for (int j = 0; j < 1005; j++) {
10
        Arrays.fill(dp[i][j], -1);
11
      }
12
    }
13
    int pos = f(0, 0, nums, -1);
14
    for (int i = 0; i < n; i++) {
15
      for (int j = 0; j < 1005; j++) {
16
        Arrays.fill(dp[i][j], -1);
17
      }
18
    }
19
    int neg = f(0, 1, nums, 1001);
20
    return Math.max(pos, neg);
21
  }
22

23
  int f(int i, int posPre, int a[], int prev) {
24
    if (i == n) return 0;
25
    if (dp[i][prev + 1][posPre] != -1) return dp[i][prev + 1][posPre];
26
    if (posPre == 0) {
27
      int not = f(i + 1, 0, a, prev);
28
      int take = 0;
29
      if (a[i] - prev > 0) {
30
        take = f(i + 1, 1, a, a[i]) + 1;
31
      }
32
      return dp[i][prev + 1][posPre] = Math.max(not, take);
33
    } else {
34
      int not = f(i + 1, 1, a, prev);
35
      int take = 0;
36
      if (a[i] - prev < 0) {
37
        take = f(i + 1, 0, a, a[i]) + 1;
38
      }
39
      return dp[i][prev + 1][posPre] = Math.max(not, take);
40
    }
41
  }
42
}