# My DP O(N^2) and Greedy O(N) solution with explanation

• DP:
just like finding longest subsequence in an array, we need using nums[i] to compare with the element showing before them nums[j]. if nums[i] > nums[j] then biggest longest subsequence with ending i equal to :
max( longest_subsequence(i), longest_subsequence(j+1))
But in there we have two situations, nums[i] either can be bigger then nums[j] or smaller then nums[j], so we need two DP array to save our result
the formula is following :
pos[i] = max(pos[i],neg[j]+1) : if nums[i] > nums[j]
neg[i] = max(neg[i],pos[j]+1) : if nums[i] < nums[j]

code:

``````class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

if not nums: return 0
pos , neg = [1 for i in nums], [1 for i in nums]
for i in xrange(1,len(nums)):
for j in xrange(0,i):
if nums[i] > nums[j]:
neg[i] = max(neg[i],pos[j]+1)
elif nums[i] < nums[j]:
pos[i] = max(pos[i],neg[j]+1)
return max(max(pos),max(neg))
``````

Greedy:
we discuss the problem by two different cases: Wiggle is starting with positive changing ex: [1,3,2] or negative changing ex: [3,1,2]
if we start as [1,3,2]:
if we meet the number greater than 2 such as 4 ,our list will become [1,3,2,4].
if we meet the number smaller than 2 such as 1 ,our list will become [1,3,1].
the same situation if we start as [3,1,2]
at the end, we just need to get the biggest element in this two situation

code as follows:

``````class Solution(object):
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if not nums: return 0
flag = 1
cnt = 1
def count(flag):
tmp = nums[0]
cnt = 1
for i in xrange(1,len(nums)):
if tmp < nums[i]:
if flag == 1:
flag = -1;
cnt += 1
elif tmp > nums[i]:
if flag == -1:
flag = 1
cnt += 1
tmp  = nums[i]
return cnt
return max(count(1),count(-1))
``````

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