leetcode-Wiggle Subsequence-376

For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences — the first because its first two differences are positive, and the second because its last difference is zero.

Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.

Examples

Input: [1,7,4,9,2,5]
Output: 6
The entire sequence is a wiggle sequence.

Input: [1,17,5,10,13,15,10,5,16,8]
Output: 7
There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].

Input: [1,2,3,4,5,6,7,8,9]
Output: 2

Follow up:
Can you do it in O(n) time?

����̰�ĺ�DP������

̰�IJ���1��3����Ϊһ���ֲ�������

�������ȥ���м���ô�㣬ֻ����3������б���Ƿ�������������3��������¼�±꣬��¼�߼���3������������

ABCʱ ̰�IJ���ȥ��B,��֤�����ȥ��A ��ôA֮ǰ����������ˣ�������õ����Ž⣬Cͬ�������ȥ��B������

ͬ��ACDʱȥ��C��……

贪心解法一（三指针）

if (nums.size() == 0)return 0;
		if (nums.size() == 1)return 1;
		if (nums.size() == 2)
		{
			if (nums[0] == nums[1])return 1;
			return 2;
		}


		int ret = 1;
		if (nums[0] != nums[1] && nums[1] != nums[2] && nums[2] != nums[0])ret++;
		int d = nums[2] - nums[1];

		int a = 2;
		int b = 1;
		int c = 0;
		int d2 = 0;
		for (int i = 2; i < nums.size(); i++)
		{
			a = i;

			d2 = nums[b] - nums[c];
			int d1 = nums[a] - nums[b];

			if (d1*d2 < 0)
			{
				ret++;
				d = a - b;
			}
			if (d2 != 0 && d1 != 0)
			{
				c = b;//V���ߵ�V�����
				b = a;
			}
			else
			{
				if (d1 == 0 && d2 != 0){  b=a; }

				if (d2 == 0 && d1 != 0){ ret++; b = a;  }



			}
		}
		return ret;

���и���ķ�������ϸ��������1,3�����У�a,b���Ժ�Ϊһ���㣬��c���Լ�¼��һ����Ч���ֵ�index

贪心解法二（双指针简化）

if (nums.size() < 2) return nums.size();

		int p = 0, len = 1;

		for (int i = 0; i < nums.size() - 1; ++i)
		{
			if (nums[i] == nums[i + 1]) continue;

			if ((nums[i] - nums[p])*(nums[i + 1] - nums[i]) <= 0) p = i, ++len;
		}

		return len;