# O(n^2) DP and O(n) Greedy solution

``````class Solution(object):
# O(n^2) DP dp[i] => subsequence ends at nums[i] (nums[i] included)
def wiggleMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dp = [1 for _ in range(len(nums))]
dp1 = [1 for _ in range(len(nums))]
ans = 1
for i in xrange(1, len(nums)):
for j in xrange(0, i):
if dp[j] % 2 == 0 and nums[i] < nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
if dp[j] % 2 == 1 and nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
if dp1[j] % 2 == 0 and nums[i] > nums[j]:
dp1[i] = max(dp1[i], dp1[j] + 1)
if dp1[j] % 2 == 1 and nums[i] < nums[j]:
dp1[i] = max(dp1[i], dp1[j] + 1)
ans = max(ans, dp[i], dp1[i])
return ans if len(nums) else 0

# Greedy: count turning points and ignore monotonic areas

def wijggleMaxLength(self, nums):
mono = None
ans = 1
for i in xrange(1, len(nums)):
diff = nums[i] - nums[i - 1]
if diff == 0: continue
if (not mono) or (mono and diff * mono < 0):
ans += 1
mono = diff
return ans if len(nums) else 0
``````

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