# Java DP O(n^2) solution

• Define state dp[i]: ends with ith element, the maximum length wiggle subsequence. sign[i] means whether ith greater than previous one.
Dp[i] = Max( dp[j] + 1 if (sign[j] > 0 and nums[i] < nums[j] or sign[j] < 0 and nums[i] > nums[j] or sign[j] == 0) for j from i - 1 to 0.

public class Solution {

``````public int wiggleMaxLength(int[] nums) {
if (nums.length < 2) return nums.length;

int[] dp = new int[nums.length];
Arrays.fill(dp, 1);

int[] sign = new int[nums.length];

for (int i = 1; i < nums.length; i++) {
for (int j = i - 1; j >= 0; j--) {
/* handle duplicate element: it means that one won't contribute to the final result */
if ((j > 0 && nums[j] == nums[j - 1]) || (nums[i] == nums[j])) {
continue;
}
if ((sign[j] > 0 && nums[i] < nums[j]) || (sign[j] < 0 && nums[i] > nums[j]) || sign[j] == 0) {
if (dp[i] < dp[j] + 1) {
if (nums[i] != nums[j]) {
sign[i] = nums[i] > nums[j] ? 1 : -1;
}
dp[i] = dp[j] + 1;
}
}
}
}

int v = Integer.MIN_VALUE;
for (int a : dp) {
v = Math.max(v, a);
}

return v;
}
``````

}

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.