Very Simple Java Solution with detail explanation

• @llkk Here I tried to prove greedy solution: check if it helps.

Suppose the given input sequence is `[a0, a1, a2, ... , ai, ... , an]`

Say our greedy solution will always pick `a0` into our final answer (according to algorithm given). And what we treat it, as an up element or a down element, is determined by comparing it with `a1`.

Let's assume `a0 < a1`, so we are treating `a0` as a down element.

Now consider there is an optimal solution (opt) sequence starting with `ai (0 <= i <= n)`.

If `ai` is considered as an up element by opt, then we must have `a0 >= ai`, otherwise by appending `a0` we can have a better solution sequence. The same idea when `ai` is treated as down element by opt.

Thus, we can always replace `ai` with `a0` so that we have another solution which is still optimal. Denote the new optimal solution with opt'.

In opt`, if `a0` is treated as up element, because `a1` is larger than `a0` according to our assumption, by replacing `aj` , which is the second element in opt', with `a1` in opt' we can have another optimal solution opt''. Because we are picking both `a0` and `a1` and opt'' is also picking them, this will cause induction.

if `a0` is treated as down element, which is the same as our solution, we can delete `a0` from input and start running both our algorithm and opt' from `a1` instead. This will also cause induction.

Omit the details of proving induction...

• I ran your code for input [1,17,5,10,7,3,4,2,3] although it outputs the correct max length. it picks up the wrong elements. I used sysout in both conditions to check which elements were being written to num using result. For the above it outputs 5 10 7 4 2 3 on console. It is incorrect because of the last three elements. It would be great if you could clarify how your code picks up 7 instead of 5 in the above input to correctly output max length as 8. Because it you choose both 10 and 7 te max length comes down to 5.

• the keshavk's solution said : it can store the series too.
but, it does not .
for example:
input :2,1,4,5,6,3,3,4,8,4
output: 2, 1, 4, 3, 4, 4

the last two nums does not satisified

• This is greedy, not dp.

``````    public int wiggleMaxLength(int[] nums) {
int n = nums.length;
if(n <= 1) return n;
int i = 1;
for(; i < n; i++){
if(nums[i] != nums[i - 1]) break;
}
if(i == n) return 1;
boolean isIncreasing = nums[i] > nums[i - 1];
i++;
int max = 2;
for(; i < n; i++){
if(isIncreasing && nums[i] < nums[i - 1]) {
max++;
isIncreasing = false;
} else if(!isIncreasing && nums[i] > nums[i - 1]){
max++;
isIncreasing = true;
}
}
return max;
}``````

• I used the feature 1 * -1 = -1 and -1 * -1 = 1, to decide whether the next difference should be positive or negative.
e.g.:
`1 (-1) 2 (1) 1 (-1) 3` the first two 1 and 2, the sign = 1, so next one should be less then 2, ie. (x - 1) * sign = -1. coz the 3rd is 1, which fits the condition. So the length of the longest subsequence + 1.

``````    public int wiggleMaxLength(int[] nums) {

if (null == nums || 0 == nums.length) return 0;

// record previous sign : + / -
int sign = 0;
// record the length of longest subseq
int sum = 1;

for (int i = 1; i < nums.length; i ++) {
if (nums[i] == nums[i - 1]) continue;
if (sign == 0) {
sign = (nums[i] - nums[i - 1]) > 0 ? 1 : -1;
sum ++;
}
else {
if ((nums[i] - nums[i - 1]) * sign < 0){
sum ++;
sign *= -1;
}
}
}

return sum;
}
``````

• At the beginning I thought it is a question about DF that the sequence can be"+ - + - + -" or "- + - + - +" .But then I found the question can convert to a greedy question. When the sequence starts as this pattern like "+ - + - + -",that means the best pattern is this.

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