# C++ 0ms O(N) dynamic programming solution

• ``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size = nums.size();

if (size == 0) {
return 0;
}

/** up[i] is the length of a longest wiggle subsequence of {nums[0],...,nums[i]}, with a
positive difference between its last two numbers. This subsequence may or may not
include nums[i] and there may be several such subsequences (of the same length).
We call this a subsequence of type U.
*/
vector<int> up(size, 0);
/** down[i] is the length of a longest wiggle subsequence of {nums[0],...,nums[i]}, with a
negative difference between its last two numbers. This subsequence may or may not
include nums[i] and there may be several such subsequences (of the same length).
We call this a subsequence of type D.
*/
vector<int> down(size, 0);

// At i=0, there is only one number and we can use it as a subsequence, i.e up[0]=down[0]=1
up[0] = 1;
down[0] = 1;
for(int i=1; i<size; ++i){

if (nums[i] > nums[i-1]) {
/** If nums[i] > nums[i-1], then we can use nums[i] to make a longer subsequence of type U
Proof: We consider a subsequence of type D in {0,...,i-1} (its length is down[i-1]).
Let N be the last number of this subsequence.
- If nums[i] > N, then we can add nums[i] to the subsequence and it gives us a longer
valid subsequence of type U.
- If nums[i] <= N, then:
(1) N cannot be nums[i-1], because nums[i-1] < nums[i] <= N i.e. nums[i-1] < N
(2) We can replace N with nums[i-1] (we still have a valid
subsequence of type D since N >= nums[i] > nums[i-1] i.e. N > nums[i-1]),
and then add nums[i] to the subsequence, and we have a longer subsequence of type U.
Therefore up[i] = down[i-1] + 1

There is no gain in using nums[i] to make a longer subsequence of type D.
Proof: Let N be the last number of a subsequence of type U
in {0,...,i-1}.
Assume we can use nums[i] to make a longer subsequence of type D. Then:
(1) N cannot be nums[i-1], otherwise we would not be able to use nums[i]
to make a longer subsequence of type D as nums[i] > nums[i-1]
(2) Necessarily nums[i] < N, and therefore nums[i-1] < N since nums[i-1] < nums[i].
But this means that we could have used nums[i-1] already to make a longer
subsequence of type D.
So even if we can use nums[i], there is no gain in using it, so we keep the old value of
down (down[i] = down[i-1])
*/
up[i] = down[i-1] + 1;
down[i] = down[i-1];
}
else if (nums[i] < nums[i-1]) {
/** The reasoning is similar if nums[i] < nums[i-1] */
down[i] = up[i-1] + 1;
up[i] = up[i-1];
}
else {
/** if nums[i] == nums[i-1], we cannot do anything more than what we did with
nums[i-1] so we just keep the old values of up and down
*/
up[i] = up[i-1];
down[i] = down[i-1];
}
}
return max(up[size-1], down[size-1]);
}
};
``````

• Thanks for your concise solution!
Explanations below help me figure out the detail.

In the first paragraph of the comment, If nums[i] <= N case:

1. down[i-1] ends up with nums[i-1] then N should be nums[i-1].Clearly, up[i] = down[i-1]+1
2. down[i-1] ends up with N which is not nums[i-1].You may assume that there is a M which is before N is greater than N i.e. M > N > nums[i] > nums[i-1].So we can replace N with nums[i-1] then M goes down to nums[i-1] rather than N and nums[i-1] goes up to nums[i].So we have a valid subsequence of type U which ends up with M -> nums[i-1] -> nums[i].

Maybe it's verbose...

• Thanks for your reply. Your (2) helps but I am not sure about your (1). If nums[i] <= N, then N cannot be nums[i-1], because nums[i-1] < nums[i] <= N i.e. nums[i-1] < N. I've updated the proof.

• @adpa Yes you are right! My mistake

Thanks for your solution. I think u can make it even simpler

``````int wiggleMaxLength(vector<int>& nums) {
int size = nums.size();
if (size == 0) return 0;
int up = 1, down = 1;

for (int i = 1; i < size; ++i) {
if (nums[i] > nums[i-1]) {
up = down + 1;
} else if (nums[i] < nums[i-1]) {
down = up + 1;
}
}
return max(up, down);
}
``````

• ``````class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int size = nums.size();

if (size == 0) {
return 0;
}

/** up[i] is the length of a longest wiggle subsequence of {nums[0],...,nums[i}}, with a
positive difference between its last two numbers. This subsequence may or may not
include nums[i] and there may be several such subsequences (of the same length).
We call this a subsequence of type U.
*/
vector<int> up(size, 0);
/** down[i] is the length of a longest wiggle subsequence of {nums[0],...,nums[i}}, with a
negative difference between its last two numbers. This subsequence may or may not
include nums[i] and there may be several such subsequences (of the same length).
We call this a subsequence of type D.
*/
vector<int> down(size, 0);

// At i=0, there is only one number and we can use it as a subsequence, i.e up[0]=down[0]=1
up[0] = 1;
down[0] = 1;
for(int i=1; i<size; ++i){

if (nums[i] > nums[i-1]) {
/** If nums[i] > nums[i-1], then we can use nums[i] to make a longer subsequence of type U
We first use a subsequence of type D in {0,...,i-1} (its length is down[i-1]).
Let N be the last number of this subsequence.
If nums[i] > N, then we can add nums[i] to the subsequence and it gives us a longer
valid subsequence of type U.
If nums[i] <= N, then we can replace N with nums[i-1] (we still have a valid
subsequence of type D since N >= nums[i] > nums[i-1] i.e. N > nums[i-1]),
and then add nums[i] to the subsequence, and we have a longer subsequence of type U.
Therefore up[i] = down[i-1] + 1

There is no gain in using nums[i] to make a longer subsequence of type D.
Proof: Let N be the last number of a subsequence of type U
in {0,...,i-1}.
Assume we can use nums[i] to make a longer subsequence of type D. Then:
(1) N cannot be nums[i-1], otherwise we would not be able to use nums[i]
to make a longer subsequence of type D as nums[i] > nums[i-1]
(2) Necessarily nums[i] < N, and therefore nums[i-1] < N since nums[i-1] < nums[i].
But this means that we could have used nums[i-1] already to make a longer
subsequence of type D.
So even if we can use nums[i], there is no gain in using it, so we keep the old value of
down (down[i] = down[i-1])
*/
up[i] = down[i-1] + 1;
down[i] = down[i-1];
}
else if (nums[i] < nums[i-1]) {
/** The reasoning is similar if nums[i] < nums[i-1] */
down[i] = up[i-1] + 1;
up[i] = up[i-1];
}
else {
/** if nums[i] == nums[i-1], we cannot do anything more than what we did with
nums[i-1] so we just keep the old values of up and down
*/
up[i] = up[i-1];
down[i] = down[i-1];
}
}
return max(up[size-1], down[size-1]);
}
};
``````

• very solid analysis!

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