Need help forming DP logic


  • 0
    T

    Here is my code so far:

    class Solution(object):
        def wiggleMaxLength(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            if len(nums) in [0, 1]: return len(nums)
            subsequence_lengths = [0 for i in range(len(nums) + 1)]
            subsequence_lengths[0] = 0
            subsequence_lengths[1] = 1
            diffs = []
            diffs = [0 for i in range(len(nums))]
            
            for j in range(1, len(nums)):
                diffs[j] = nums[j] - nums[j-1]
            
            for k in range(2, len(nums) + 1):
                if (diffs[k] < 0 and diffs[k-1] > 0) or (diffs[k] > 0 and diffs[k-1] < 0):
                    subsequence_lengths[k] = subsequence_lengths[k-1] + 1
                else:
                    subsequence_lengths[k] = subsequence_lengths[k-1]
            print subsequence_lengths
            return subsequence_lengths[-1]
                
    

    I make an array called subsequence_lengths that for every i subsequence_lengths[i] returns the length of the longest subsequence that can be formed from using the first i characters oof nums. so subsequence_lengths[0] = 0 because only subsequences of length 0 can be formed from the first i characters of nums. I keep getting an error because of the difference in size between my diffs array and subsequence_lengths array. diffs just tells me the differences between the values in nums. If i iterate to len(nums) + 1, i get an indexoutofbound error, but if I iterate to len(nums) subsequence_lengths is incomplete and returns the wrong answer.

    please help me figure out where im going wrong.


Log in to reply
 

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