# Java 7ms, DFS

• This solution is inspired by longest increasing sequence problem.
Idea is to maintain the longest '+' and '-' sequence for each value, starting from end. If the value is already computed return the value and compare.
This is O(n^2) solution, will try next for a better solution.

``````public class Solution
{
//0 for Pos, 1 for neg
int [][] tempArr;
public int wiggleMaxLength(int[] nums)
{
if(nums == null || nums.length == 0)
return 0;
tempArr = new int[nums.length][];
for(int i = 0; i < nums.length; i++)
{
tempArr[i] = new int[2];
tempArr[i][0] = tempArr[i][1] = -1;
}
int[] maxVal = new int[2];
maxVal[0] = maxVal[1] = -1;
tempArr[nums.length - 1][0] = tempArr[nums.length - 1][1] = 0;
for(int i = nums.length - 1; i >=0; i--)
{
wiggle(nums, i);
maxVal[0] = Math.max(tempArr[i][0], maxVal[0]);
maxVal[1] = Math.max(tempArr[i][1], maxVal[1]);
}
int retVal = Math.max(maxVal[0], maxVal[1]);
return retVal == -1? 0: retVal + 1;
}
void wiggle(int[] nums, int ind)
{
if(tempArr[ind][0] != -1 || tempArr[ind][1] != -1)
return;
int[] tempVal = new int[2];
tempVal[0] = tempVal[1] = -1;
for(int i = ind + 1; i < nums.length; i++)
{
if(nums[ind] != nums[i])
wiggle(nums, i);
if(nums[ind] < nums[i])
tempVal[0] = Math.max(tempVal[0], tempArr[i][1]); //toggle compare current + with -, and vice versa.
else if(nums[ind] > nums[i])
tempVal[1] = Math.max(tempVal[1], tempArr[i][0]);
}
tempArr[ind][0] = tempVal[0] == -1? tempVal[0]: tempVal[0] + 1;
tempArr[ind][1] = tempVal[1] == -1? tempVal[1]: tempVal[1] + 1;
}
}``````

• Updating the solution to do it in single pass: https://discuss.leetcode.com/topic/51870/java-o-n-0-ms
Yes, the order doesn't matter and only the relative increase or decrease matters.

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