You should know the key idea of the O(n) algorithm


  • 0
    A

    Ok, the idea is quite simple: remove the elements between a increase or decrease or equal segment, the remain elements will be a longest wiggle subsequence.

    such as [1, 2, 3,4] is a increase segment, we remove the elements between it get [1, 4]
    similarly [4, 3, 2, 1] => [4, 1]
    and equal segment we only remain one of them, ex, [1,1,1] => [1]

    why does it works?
    think about it: if you get a solution which has elements in a increase or decrease or equal segment, you can replace the these elements by the first or the last element of the segment and the length of the solution remain same.So the elements between a segment is no useful.And the remain elements can compose of a solution, obviously it is the longest.

    All the O(N) solution is based by this idea. Since we only need the length of the solution, we only need count the elements in the two ends of a segment.

    class Solution(object):
    def wiggleMaxLength(self, nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    inc = None
    nums = [nums[i] for i in xrange(len(nums)) if i == 0 or nums[i] != nums[i-1]]
    if len(nums) <= 1:
    return len(nums)
    cnt = 2
    for i in xrange(1, len(nums) - 1):
    if not (nums[i - 1] > nums[i] > nums[i + 1] or
    nums[i - 1] < nums[i] < nums[i + 1]):
    cnt +=1
    return cnt


Log in to reply
 

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