Java 7ms, DFS


  • 0
    V

    This solution is inspired by longest increasing sequence problem.
    A wiggle can start with '+', or with a '-'.
    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;
        }
    }

  • 0
    V

    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.


Log in to reply
 

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