NC83 连续子数组的最大乘积 - 借助二维数组

本题解题方法纯属猜试得出，事先没有把握一定能有解。

设想开二维数组，

1）用其中一维记录以0分割的每一段的积，例如 [2, 3, 0, -1, 2, 0, 3, 5, 6]，则记录为 [2, 6, 0, -1, -2, 0, 3, 15, 90]，可见目前得到的结果很局限，更多是针对正数段，或者偶数个数的负数段。

2）另一维记录动态删减过程，例子同上，记录为 [2, 6, 0, -1, 2, 0, 3, 15, 90]，重点体现在第二维数组受第一维结果影响，在每一段计算乘积过程中，如果第一维得到的新结果小于当前元素值，并且第二维结果也小于当前元素值，那么第二维结果需要抛弃当前指针k所在的元素，以实现大于或等于当前值的目的。

还是不喜欢写注释！

class Solution:
    def maxProduct(self , nums: List[int]) -> int:
        # write code here
        if len(nums) == 1: return nums[-1]
        dp = [[0]*len(nums) for _ in range(2)]
        dp[0][0] = nums[0]
        dp[1][0] = nums[0]
        k = 0
        for i in range(1,len(nums)):
            if dp[0][i-1]*nums[i] >= nums[i]:
                dp[0][i] = dp[0][i-1]*nums[i]
                dp[1][i] = dp[1][i-1]*nums[i]

            if dp[0][i-1]*nums[i] < nums[i]:
                dp[0][i] = dp[0][i-1]*nums[i]
                if dp[1][i-1]*nums[i] < nums[i]:
                    dp[1][i] = (dp[1][i-1]*nums[i])//nums[k]
                    k = k + 1
                else:
                    dp[1][i] = dp[1][i-1]*nums[i]
                
            if dp[0][i-1] == dp[1][i-1] == 0 and nums[i] != 0:
                dp[0][i], dp[1][i] = nums[i], nums[i]
                k = i
                
        return max(max(dp[0]), max(dp[1]))