## 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```

Can you do it in O(n) time?

ABC时 贪心策略去掉B,反证：如果去掉A 那么A之前的上限提高了，更不会得到更优解，C同理，因此去掉B是最优

``````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;``````

``````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;``````

### 梦想游戏人

Leetcode 376. Wiggle Subsequence

SnailTyan
2018/08/13
0
0

2017/12/28
0
0
leetcode-392. Is Subsequence-DP-NORMAL

Given a string s and a string t, check if s is subsequence of t. You may assume that there is only lower case English letters in both s and t. t is potentially a very long (leng......

2016/09/17
24
0
Leetcode 873:最长递增斐波那契子序列

Flying_sfeng
03/03
0
0
Leetcode 674. Longest Continuous Increasing Subsequence

SnailTyan
2018/10/25
0
0

C++ vector和list的区别

1.vector数据结构 vector和数组类似，拥有一段连续的内存空间，并且起始地址不变。 因此能高效的进行随机存取，时间复杂度为o(1); 但因为内存空间是连续的，所以在进行插入和删除操作时，会造...

shzwork
52分钟前
2
0
Spring之invokeBeanFactoryPostProcessors详解

Spring的refresh的invokeBeanFactoryPostProcessors，就是调用所有注册的、原始的BeanFactoryPostProcessor。 相关源码 public static void invokeBeanFactoryPostProcessors(Configu......

cregu

3
0
ibmcom/db2express-c_docker官方使用文档

(DEPRECIATED) Please check DB2 Developer-C Edition for the replacement. What is IBM DB2 Express-C ? ``IBM DB2 Express-C``` is the no-charge community edition of DB2 server, a si......

BG2KNT

2
0
Ubuntu 18.04.2 LTS nvidia-docker2 : 依赖: docker-ce (= 5:18.09.0~3-0~ubuntu-bionic)

Pulsar-V

4
0

4
0