[Python] Easy to understand DP
Algorithm:\n\nWe can simplify the problem:\n1. subarry is continuous, so we can transfer the problem to: For each index i n nums , what is the max length of sub
**Algorithm:**\n\nWe can simplify the problem:\n1. subarry is continuous, so we can transfer the problem to: For each index **i** n **nums** , what is the max length of subarray (ending with index i) With positive product. Then we can iterate every answer for all indexes to get the result for original question.\n2. We know that: `positive_number * positive_number` is positive, `positive_number * negative_number` is negative, `negative_number * negative_number` is positive. \n\nLet\'s define:\n`dp[i][0] : max length of subarray ending with index i With positive product`\n`dp[i][1] : max length of subarray ending with index i With negative product`\n\nIn order to get the answer for current index, we need **dp[i - 1][0]** and **dp[i - 1][1]** to form a new subarray.\n\n**Implementation:**\n\ndefine a 2D array with length n\n\nBase case would be: when index is 0, only one number can be used\n\nLoop through the array, for the new number we have:\n1.  if current number is positive, we know we can definitely form a positive subarry, the length is at least 1:\n\t\t`[previous positive subarray] + [current number positive]`\n2.  if current number is positive, we know we can form a negative subarray if for previous index, negative subarray exists. Otherwise we can\'t form a negetive subarray ending with current number\n\t\t`[previous negative subarray] + [current number positive]`\n3.  if current number is negative, we know we can definitely form a negative subarry, the length is at least 1:\n\t\t`[previous positive subarray] + [current number negative]`\n4.  if current number is negative, we know we can form a positive subarray if for previous index, negative subarray exists. Otherwise we can\'t form a positive subarray ending with current number\n\t\t`[previous negative subarray] + [current number negative]`\n\n\n```\n    def getMaxLen(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        n = len(nums)\n        dp = [[0] * 2 for _ in range(n)]   \n        # dp[i][0] : max length of subarray ending with index i With positive product   \n\t\t# dp[i][1] : max length of subarray ending with index i With negative product \n\t\t\n        # Base case: when index is 0, only one number can be used\n        if nums[0] > 0:\n            dp[0][0] = 1\n        \n        if nums[0] < 0:\n            dp[0][1] = 1\n            \n        res = dp[0][0]\n        \n        for i in range(1, n):\n            cur = nums[i]\n            \n            if cur > 0:\n                dp[i][0] = dp[i - 1][0] + 1\n                if dp[i - 1][1] > 0: # if previous negative subarray exists\n                    dp[i][1] = max(dp[i][1], dp[i - 1][1] + 1)\n            if cur < 0:\n                dp[i][1] = dp[i - 1][0] + 1\n                if dp[i - 1][1] > 0: # if previous negative subarray exists\n                    dp[i][0] = max(dp[i][0], dp[i - 1][1] + 1)\n                    \n            res = max(res, dp[i][0])\n            \n        return res\n```\nSpace: **O(n)** Time: **O(n)**\n\n\nFurthermore, we can use rotating array to reduce the space complexity:\n```\n    def getMaxLen(self, nums):\n        """\n        :type nums: List[int]\n        :rtype: int\n        """\n        n = len(nums)\n        dp = [0] * 2\n\n        if nums[0] > 0:\n            dp[0] = 1\n        \n        if nums[0] < 0:\n            dp[1] = 1\n            \n        res = dp[0]\n        \n        for i in range(1, n):\n            cur = nums[i]\n            tmp = [0] * 2\n            if cur > 0:\n                tmp[0] = dp[0] + 1\n                if dp[1] > 0:\n                    tmp[1] = max(tmp[1], dp[1] + 1)\n            elif cur < 0:\n                tmp[1] = dp[0] + 1\n                if dp[1] > 0:\n                    tmp[0] = max(tmp[0], dp[1] + 1)\n            dp = tmp\n            res = max(res, dp[0])\n            \n        return res\n```\nSpace: **O(1)** Time: **O(n)**
['Dynamic Programming', 'Python']