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[i1]) {
/** If nums[i] > nums[i1], then we can use nums[i] to make a longer subsequence of type U
Proof: We consider a subsequence of type D in {0,...,i1} (its length is down[i1]).
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[i1], because nums[i1] < nums[i] <= N i.e. nums[i1] < N
(2) We can replace N with nums[i1] (we still have a valid
subsequence of type D since N >= nums[i] > nums[i1] i.e. N > nums[i1]),
and then add nums[i] to the subsequence, and we have a longer subsequence of type U.
Therefore up[i] = down[i1] + 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,...,i1}.
Assume we can use nums[i] to make a longer subsequence of type D. Then:
(1) N cannot be nums[i1], otherwise we would not be able to use nums[i]
to make a longer subsequence of type D as nums[i] > nums[i1]
(2) Necessarily nums[i] < N, and therefore nums[i1] < N since nums[i1] < nums[i].
But this means that we could have used nums[i1] 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[i1])
*/
up[i] = down[i1] + 1;
down[i] = down[i1];
}
else if (nums[i] < nums[i1]) {
/** The reasoning is similar if nums[i] < nums[i1] */
down[i] = up[i1] + 1;
up[i] = up[i1];
}
else {
/** if nums[i] == nums[i1], we cannot do anything more than what we did with
nums[i1] so we just keep the old values of up and down
*/
up[i] = up[i1];
down[i] = down[i1];
}
}
return max(up[size1], down[size1]);
}
};
C++ 0ms O(N) dynamic programming solution


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:
 down[i1] ends up with nums[i1] then N should be nums[i1].Clearly, up[i] = down[i1]+1
 down[i1] ends up with N which is not nums[i1].You may assume that there is a M which is before N is greater than N i.e. M > N > nums[i] > nums[i1].So we can replace N with nums[i1] then M goes down to nums[i1] rather than N and nums[i1] goes up to nums[i].So we have a valid subsequence of type U which ends up with M > nums[i1] > nums[i].
Maybe it's verbose...


Hi adpa,
Thanks for your solution. I think u can make it even simplerint 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[i1]) { up = down + 1; } else if (nums[i] < nums[i1]) { down = up + 1; } } return max(up, down); }

@adpa said in 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[i1]) { /** If nums[i] > nums[i1], then we can use nums[i] to make a longer subsequence of type U We first use a subsequence of type D in {0,...,i1} (its length is down[i1]). 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[i1] (we still have a valid subsequence of type D since N >= nums[i] > nums[i1] i.e. N > nums[i1]), and then add nums[i] to the subsequence, and we have a longer subsequence of type U. Therefore up[i] = down[i1] + 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,...,i1}. Assume we can use nums[i] to make a longer subsequence of type D. Then: (1) N cannot be nums[i1], otherwise we would not be able to use nums[i] to make a longer subsequence of type D as nums[i] > nums[i1] (2) Necessarily nums[i] < N, and therefore nums[i1] < N since nums[i1] < nums[i]. But this means that we could have used nums[i1] 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[i1]) */ up[i] = down[i1] + 1; down[i] = down[i1]; } else if (nums[i] < nums[i1]) { /** The reasoning is similar if nums[i] < nums[i1] */ down[i] = up[i1] + 1; up[i] = up[i1]; } else { /** if nums[i] == nums[i1], we cannot do anything more than what we did with nums[i1] so we just keep the old values of up and down */ up[i] = up[i1]; down[i] = down[i1]; } } return max(up[size1], down[size1]); } };