o(n) java greedy


  • 0
    Z
    public int wiggleMaxLength(int[] nums) {
    		if (nums.length<2){return nums.length;}
    		int[] t = new int[nums.length];
    		t[0] = nums[0];
    		int direction = 1;
    		int i;
    		for( i = 1; i<nums.length; i++){if(nums[i]!= t[0]){ t[1] = nums[i]; break;}}
    		direction = t[1]-t[0];
    		int cur = 1;
    		for(int j = i+1; j<nums.length; j++){
    			if ((nums[j]-t[cur])*(direction)>=0){
    				t[cur] = nums[j]; 
    				
    			}
    			else{
    				direction = nums[j]-t[cur];
    				t[++cur] = nums[j]; 
    			}
    		}
    		return cur+1;
        }
    

Log in to reply
 

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