Analysis and easy to understand C++ solution


  • 0
    W

    Observations:

    • If there are more than two (assuming n) continuous positives in the difference sequence, which means the subsequence is monoly increasing, we can keep only one. Same for the case of more than two continuous negatives.
    • If there is a zero in the difference sequence, we can simply just remove it since it won't change the increasing or decreasing state but will certainly change the length of a subsequence of continuous positives or negatives

    Algorithm:

    • Calculate the difference sequence
    • Traverse the difference sequence and combine continuous positives into one positive (if 0 is in the middle, simply ignore it). Do the same combination for continuous negative until the end.
    • Count the remaining numbers n in the combined sequence, the length of the longest subsequence is simply n+1

    Complexity
    Time required is 2(n-1)* where n is the list length, so time complexity is O(n), i.e. linear time

    int getSign(const int& v)
    {
            if (v > 0) return 1;
            if (v < 0) return -1;
            return 0;
    }
    int wiggleMaxLength(vector<int>& nums)
    {
    	int len = nums.size();
    	if (len == 0) return 0;
    	if (len == 1) return 1;
    	if (len == 2) {
    		if (nums[0] == nums[1]) return 1;
    		else return 2;
    	}
    	//compute the difference sequence
    	int i;
    	vector<int> d;
    	for (i = 1; i < len; ++i) {
    		d.push_back(nums[i] - nums[i - 1]);
    	}
    	//now virtually combine the continuous positives and negatives together
    	//find the first non-zero value in the difference sequence
    	for (i = 0; i < len - 1; i++) {
    		if (d[i] != 0) break;
    	}
    	if (i == len - 1) return 1; //the whole sequence contains one single number
    	int count = 1;
    	int preSign = getSign(d[i]);
    	for (int j = i + 1; j < len - 1; ++j) {
    		int curSign = getSign(d[j]);
    		if (curSign != 0 && curSign != preSign){
    			count++;
    			preSign = curSign;
    		}
    	}
    	return count + 1;
    }
    

Log in to reply
 

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