<p>A <strong>wiggle sequence</strong> is a sequence where the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with one element and a sequence with two non-equal elements are trivially wiggle sequences.</p>

<ul>
	<li>For example, <code>[1, 7, 4, 9, 2, 5]</code> is a <strong>wiggle sequence</strong> because the differences <code>(6, -3, 5, -7, 3)</code> alternate between positive and negative.</li>
	<li>In contrast, <code>[1, 4, 7, 2, 5]</code> and <code>[1, 7, 4, 5, 5]</code> are not wiggle sequences. The first is not because its first two differences are positive, and the second is not because its last difference is zero.</li>
</ul>

<p>A <strong>subsequence</strong> is obtained by deleting some elements (possibly zero) from the original sequence, leaving the remaining elements in their original order.</p>

<p>Given an integer array <code>nums</code>, return <em>the length of the longest <strong>wiggle subsequence</strong> of </em><code>nums</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,7,4,9,2,5]
<strong>Output:</strong> 6
<strong>Explanation:</strong> The entire sequence is a wiggle sequence with differences (6, -3, 5, -7, 3).
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,17,5,10,13,15,10,5,16,8]
<strong>Output:</strong> 7
<strong>Explanation:</strong> There are several subsequences that achieve this length.
One is [1, 17, 10, 13, 10, 16, 8] with differences (16, -7, 3, -3, 6, -8).
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,3,4,5,6,7,8,9]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 1000</code></li>
	<li><code>0 &lt;= nums[i] &lt;= 1000</code></li>
</ul>

<p>&nbsp;</p>
<p><strong>Follow up:</strong> Could you solve this in <code>O(n)</code> time?</p>

class Solution:
    def wiggleMaxLength(self, nums: List[int]) -> int:
        # Consider: 
        # Longest wiggle 1 to i-1
        # State:
        # Negative last. Postive Last.

        dp = [[[None, None], [None, None]] for i in range(len(nums))] 
        dp[0] = [
            [nums[0], 1], #positives
            [nums[0], 1] #negatives
        ]
        
        for i in range(1, len(nums)):
            current_integer = nums[i]

            best_negative = None
            for j in range(i):
                p_int, p_len = dp[j][0] # coming from positive

                if current_integer < p_int:
                    possibility = [current_integer, p_len+1]
                else:
                    possibility = dp[j][1]

                if best_negative == None or best_negative[1] < possibility[1]:
                    best_negative = possibility
            dp[i][1] = best_negative

            best_positive = None
            for j in range(i):
                p_int, p_len = dp[j][1] # coming from negative

                if current_integer > p_int:
                    possibility = [current_integer, p_len+1]
                else:
                    possibility = dp[j][0]

                if best_positive == None or best_positive[1] < possibility[1]:
                    best_positive = possibility
            dp[i][0] = best_positive


            # best_negative = None
            # best_positive = None
            # for j in range(i):
            #     positive = dp[j][0]
            #     negative = dp[j][1]
            #     # print(positive, negative)

            #     p_int, p_len = positive
            #     if current_integer > p_int:
            #         possibility = [current_integer, p_len+1]
            #     else:
            #         possibility = [p_int, p_len]

            #     if best_negative == None or best_negative[1] < possibility[1]:
            #         best_negative = possibility

            #     p_int, p_len = negative
            #     if current_integer < p_int:
            #         possibility = [current_integer, p_len+1]
            #     else:
            #         possibility = [p_int, p_len]

            #     if best_positive == None or best_positive[1] < possibility[1]:
            #         best_positive = possibility

            # dp[i][0] = best_negative
            # dp[i][1] = positive


        return max(dp[len(nums)-1][1][1], dp[len(nums)-1][0][1])



            # for j in range(i):
            #     print(dp, i, j)
            #     p_int, p_len = dp[j][0][i]
            #     if current_integer < p_int:
            #         dp[i][0].append([current_integer, p_len+1])
            #     else:
            #         dp[i][0].append([p_int, p_len])

            #     p_int, p_len = dp[j][1][i]
            #     if current_integer > p_int:
            #         dp[i][1].append([current_integer, p_len+1])
            #     else:
            #         dp[i][1].append([p_int, p_len])

        # for i in range(1, len(nums)):
        #     current_integer = nums[i]
        #     dp[i] = []
            
        #     for j in range(i-1):
        #         if len(dp[j]): break
        #         prev_positive_side_integer = dp[j][0][0]
        #         prev_positive_side_length = dp[j][0][1]

        #         if current_integer < prev_positive_side_integer: # if current num < last_integer
        #             dp[i].append([current_integer, prev_positive_side_length + 1])

        #     for j in range(i-1):
        #         if len(dp[j]): break
        #         prev_negative_side_integer = dp[j][1][0]
        #         prev_negative_side_length = dp[j][1][1]

        #         if current_integer > prev_negative_side_integer: # if current num > last_integer
        #             dp[i].append([current_integer, prev_negative_side_length + 1])

        #     print(dp)

        # best = 0
        # for i in range(dp[len(nums)-1]):
        #     p = dp[len(nums)-1][0][1]
        #     n = dp[len(nums)-1][1][1]

        #     best = max(best, p, n)

        # return best

            
                

'''
nums = [1,17,5,10,13,15,10,5,16,8]

# [each num] -> [[positive side: [last_integer, length], negative side: [last_integer, length]]]
nums[0] = +[1] or -[1]

nums[1] = +[1, 17] or -[1]

nums[2] = +[1,5] or -[1,17,5]

nums[3] = +[1,17,5,10] or -[1, 17, 10]

nums[4] = +[1, 17, 10, 13] or -[1, 17, 13]
'''
16600