【LEETCODE】376- Wiggle Subsequence [Python]
タイトル:
https://leetcode.com/problems/wiggle-subsequence/
タイトル:
Given a sequence, return the length of the longest wiggle subsequence.
Wiggle sequence means that the difference between successive numbers strictly alternate between positive and negative. Notice that the difference should not be 0, the first difference can be either positive or negative, and a sequence is also a wiggle one if the length is less than or equal to 2.
考え方:
We can either apply ‘greedy’ or ‘DP’ to solve this problem.
For DP
Step 1: The structure
Let Si denote the longest subsequence when the index is i of given sequence.
So whether Si is a wiggle sequence, it depends on Si−1 is already a wiggle sequence, at the same time Si−1 and numi combine a wiggle sequence.
That means, at the point of i there can be two choices: one is, when num[i]num[i−1] , the last difference of Si−1 should be negative, then the length of Si=Si−1+1 .
So, we got the structure of this DP problem, if we want to solve the problem to find longest length of wiggle subsequence at Si , we can firstly solve subproblem of finding the longest length of wiggle subsequence at Si−1 .
Step 2: A recursive solution
According to the above structure, we should define 2 sequences p and q. p stores the longest length of wiggle subsequence at index i satisfying the last difference is positive. similarly, q stores the longest length of wiggle subsequence at index i satisfying the last difference is negative.
Then, if num[i]>num[i−1] , at least the last difference of Si−1 should be negative, so p[i]=q[i−1]+1 . Similarly, if numiIf num is null, the answer should be 0.
If length of num is larger than 0, at least the length of longest wiggle subsequence is larger or equal to 1, so we can initialize p and q with 1s.
At each step, we should choose the max length, as well as the final, we will choose between p[n−1] and q[n−1] .
Step 3: Computing the optimal costs
notice:
class def max return
nums
IndentationError:unexpected indent:インデント非標準
https://leetcode.com/problems/wiggle-subsequence/
タイトル:
Given a sequence, return the length of the longest wiggle subsequence.
Wiggle sequence means that the difference between successive numbers strictly alternate between positive and negative. Notice that the difference should not be 0, the first difference can be either positive or negative, and a sequence is also a wiggle one if the length is less than or equal to 2.
考え方:
We can either apply ‘greedy’ or ‘DP’ to solve this problem.
For DP
Step 1: The structure
Let Si denote the longest subsequence when the index is i of given sequence.
So whether Si is a wiggle sequence, it depends on Si−1 is already a wiggle sequence, at the same time Si−1 and numi combine a wiggle sequence.
That means, at the point of i there can be two choices: one is, when num[i]
So, we got the structure of this DP problem, if we want to solve the problem to find longest length of wiggle subsequence at Si , we can firstly solve subproblem of finding the longest length of wiggle subsequence at Si−1 .
Step 2: A recursive solution
According to the above structure, we should define 2 sequences p and q. p stores the longest length of wiggle subsequence at index i satisfying the last difference is positive. similarly, q stores the longest length of wiggle subsequence at index i satisfying the last difference is negative.
Then, if num[i]>num[i−1] , at least the last difference of Si−1 should be negative, so p[i]=q[i−1]+1 . Similarly, if numi
If length of num is larger than 0, at least the length of longest wiggle subsequence is larger or equal to 1, so we can initialize p and q with 1s.
At each step, we should choose the max length, as well as the final, we will choose between p[n−1] and q[n−1] .
Step 3: Computing the optimal costs
class Solution(object):
def wiggleMaxLength(self, nums):
""" :type nums: List[int] :rtype: int """
if nums==[]:
return 0
size = len(nums)
p = [1]*size
q = [1]*size
for i in range(1, size):
for j in range(i):
if nums[i]>nums[j]:
p[i] = max(p[i], q[j]+1)
elif nums[i]<nums[j]:
q[i] = max(q[i], p[j]+1)
return max(p[size-1], q[size-1])
notice:
class def max return
nums
IndentationError:unexpected indent:インデント非標準