Python O(n)by DP [w/ Comment]
Python O(n)by DP [w/ Comment]\n\n---\n\n\nclass Solution:\n    def getMaxLen(self, nums: List[int]) -> int:\n        \n        size = len(nums)\n        \n     
Python O(n)by DP [w/ Comment]\n\n---\n\n```\nclass Solution:\n    def getMaxLen(self, nums: List[int]) -> int:\n        \n        size = len(nums)\n        \n        # dp table for subarray with positive product and negative product\n        pos, neg = [0 for _ in range(size)], [0 for _ in range(size)]\n        \n        \n        # initialization on base case\n        if nums[0] > 0 :\n            pos[0] = 1\n        \n        elif nums[0] < 0 :\n            neg[0] = 1\n            \n        \n        # general cases\n        for idx, number in enumerate(nums[1:], 1):\n            \n            if number > 0:\n                \n                # positive = previous positive * positive number\n                pos[idx] = pos[idx-1] + 1\n                \n                if neg[idx-1]:\n                    # negative = previous negative * positive number\n                    neg[idx] = neg[idx-1] + 1\n            \n            elif number < 0:\n                \n                # negative = previous positive * negative number\n                neg[idx] = pos[idx-1] + 1\n                \n                if neg[idx-1]:\n                    # positive = previous negative * negative number\n                    pos[idx] = neg[idx-1] + 1\n        \n        # What we want is longest length of subarray with positive product\n        return max(pos)\n```\n\n---\n\nRewrite in top-down DP:\n\n```\nclass Solution:\n    def getMaxLen(self, nums: List[int]) -> int:\n        \n        global_pos = 0\n        \n        \n        def dp( i ):\n            \n            ## Parameter\n            # input i: ending index of array i\n            # output : length of positive product subarray, length of negative product subarray\n            \n            ## Base case:\n            if i == 0:\n                \n                if nums[0] > 0:\n                    \n                    return 1, 0, 1\n                \n                elif nums[0] < 0:\n                    return 0, 1, 0\n                \n                else:\n                    return 0, 0, 0\n            \n            \n            ## General cases\n            \n            prev_pos, prev_neg, max_pos_length = dp(i-1)\n            cur_pos, cur_neg = 0, 0\n            \n            if nums[i] > 0:\n                \n                # positive = previous positive * positive number\n                cur_pos = prev_pos + 1\n                \n                if prev_neg:\n                    # negative = previous negative * positive number\n                    cur_neg = prev_neg + 1\n                    \n            elif nums[i] < 0 :\n                \n                # negative = previous positive * negative number\n                cur_neg = prev_pos + 1\n                \n                if prev_neg:\n                    # positive = previous negative * negative number\n                    cur_pos = prev_neg + 1\n            \n            \n            max_pos_length = max(max_pos_length, cur_pos )\n            return cur_pos, cur_neg, max_pos_length\n        \n        # ----------------------------------------\n        \n        # third return value is maximum length of subarray with positive product\n        return dp( len(nums)-1 )[2]\n```\n\n---\n\nRelated leetcode challenge:\n\n[Leetcode #376 Wiggle Subsequence](https://leetcode.com/problems/wiggle-subsequence/)
['Dynamic Programming', 'Python', 'Python3']