376_摆动序列.org

题目

思路

• DP：类似于最长上升子序列这道题，只不过dp存储的是tuple，dp[i]=(a,b)表示以第i个元素结束的最长摆动序列长度为a；b表示第i个元素和前i-1个元素结束的最长摆动序列中最后一个元素的相对大小：0-相等/1-nums[k]>nums[k-1]/-1-nums[k]<nums[k-1]。

因此前i个序列的最长摆动序列为，依次判断0～i-1的元素的最长摆动序列和第i个元素的相对大小以及摆动序列的最后元素的相对大小即可。

使用两个数组up、down分别保存上升、下降的状态

其中 up[i] 存的是目前为止最长的以第 i 个元素结尾的上升摆动序列的长度，down[i] 记录的是目前为止最长的以第i个元素结尾的下降摆动序列的长度。

注：子序列可以不连续，子串要连续

code

# dp-248ms
class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:

        # 7.7 补充一种 O(n) 的dp方法：
	up = [0] * n
        down = [0] * n
        up[0], down[0] = 1, 1
        for i in range(1, n):
            if nums[i] > nums[i-1]:
                up[i] = down[i-1] + 1
                down[i] = down[i-1] # down[i] 不变
            elif nums[i] < nums[i-1]:
                down[i] = up[i-1] + 1
                up[i] = up[i-1] # up[i] 不变
            elif nums[i] == nums[i-1]:
                up[i] = up[i-1]
                down[i] = down[i-1]
        return max(up[-1], down[-1])

	# old：
        # special case
        if not nums:
            return 0
        if len(nums)==1 or (len(nums)==2 and nums[0]==nums[1]):
            return 1
        elif len(nums)==2 and nums[0]!=nums[1]:
            return 2
        dp = [(1, 0) for i in range(len(nums))]
        # base case
        if nums[1]-nums[0]<0:
            dp[1] = (2, -1) 
        elif nums[1]-nums[0] > 0:
            dp[1] = (2, 1)
        for i in range(2, len(nums)):
            for j in range(i):
	        # 和第0个元素组合的摆动序列
                if dp[j][0] == 1 and nums[i]!=nums[j]:
                    dp[i] =  (2, -1 if nums[i]<nums[j] else 1)
                    continue
		# 和第j个元素组合，且    
                if nums[i]-nums[j]>0 and dp[j][1]==-1:
                    if dp[j][0] + 1 > dp[i][0]:
                        dp[i] = (dp[j][0]+1, 1)
                    continue
                if nums[i]-nums[j]<0 and dp[j][1]==1:
                    if dp[j][0] + 1 > dp[i][0]:
                        dp[i] = (dp[j][0]+1, -1)
                    continue
                if nums[i]==nums[j]:
                    if dp[j][0] > dp[i][0]:
                        dp[i] = (dp[j][0], 0)
        return dp[len(nums)-1][0]