# O(n) DP and Stack Solution

• DP with array

``````public int wiggleMaxLength(int[] nums) {
if(nums.length==0) return 0;
int[] up = new int[nums.length];
int[] down = new int[nums.length];
Arrays.fill(up,1);
Arrays.fill(down,1);
for(int i=1;i<nums.length;i++) {
if(nums[i]>nums[i-1]) up[i] = Math.max(down[i-1] + 1,up[i-1]);
if(nums[i]<nums[i-1]) down[i] =Math.max(up[i-1] + 1,down[i-1]);
if(nums[i]==nums[i-1]) {
up[i] = up[i-1];
down[i] = down[i-1];
}
}
return Math.max(up[nums.length-1],down[nums.length-1]);
}
``````

DP without array (since we just used the previous number in the array)

``````public int wiggleMaxLength(int[] nums) {
if(nums.length==0) return 0;
int up = 1;
int down = 1;
for(int i=1;i<nums.length;i++) {
if(nums[i]>nums[i-1]) up = Math.max(down + 1,up);
if(nums[i]<nums[i-1]) down =Math.max(up + 1,down);
}
return Math.max(up,down);
}
``````

stack:

``````public int wiggleMaxLength(int[] nums) {
if(nums.length==0) return 0;
Stack<Integer> st = new Stack<>();
int up = 1;
int prev = 0;
int ans = 1;
st.push(nums[0]);
for(int i = 1;i<nums.length;i++) {
up = 0;
while(!st.isEmpty()&&st.peek()>nums[i]) {
st.pop();
up = 2;
}
if(up==0){
if(st.isEmpty()||st.peek()<nums[i]) up = 1;
}
if((up==1||up==2)&&prev!=up) {
ans++;
prev = up;
}
st.push(nums[i]);
}
return ans;
}
``````

int up: 0 - the same with the peek of stack
1 - larger than the peek of stack
2 - smaller than the peek of stack
int prev: the previous up value;

``````if you visualize the number trend (1,7,4,5,5), you can see something like:
_
/  \  /
or (1,7,4,9,2,5)

/ \ / \ / \

``````

the basic idea is quite like dp solution, if number goes up (/), find the longest length of the sequence that is end with number going down. if number goes down (\), find the longest length of the sequence that is end with number going up. ignore the same adjacent value (-).

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