Straightforward Java solution (Plain/Non-dp) 1ms with pruning


  • 0
    S
    public int wiggleMaxLength(int[] nums) {
    	int len = nums.length;
    	if(len <= 1) return len;
    	
    	int max = 1;
    	//have an array count[] to record the longest wiggle subsequence
    	int[] count = new int[len];
    	for(int i = 0; i < len; i++){
    		count[i] = 1;
    	}
    	for(int i = 1; i < len; i++){
    		if(max > i) return max;//prune
    		boolean positive = true;
    		
    		if(nums[i] > nums[i-1]) {
    			positive = true;
    			count[i]++;
    		}
    		else if(nums[i] < nums[i-1]) {
    			positive = false;
    			count[i]++;
    		}
    		else continue;//this is the case when nums[i] == nums[i-1] which is also not a valid wiggle sequence
    		
    		for(int j = i; j < len-1; j++){
    			if((nums[j+1] < nums[j] && positive) || (nums[j+1] > nums[j] && !positive)){
    				positive = !positive;
    				count[i]++;
    			}
    		}
    		
    		if(max < count[i]){
    			max = count[i];
    		}
    	}
    	return max;
    }

Log in to reply
 

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