Problem statement

https://binarysearch.com/problems/Maximal-Sublist-Product/

Solution

Equal to Leetcode 0152. Maximum Product Subarray.

Complexity

Time and space is O(n).

Code

class Solution:
    def solve(self, nums):
        N = len(nums)
        dp1 = [0] * N
        dp2 = [0] * N
        dp1[0] = dp2[0] = nums[0]
        
        for k in range(1, N):
            if nums[k] > 0:
                dp1[k] = max(dp1[k-1] * nums[k], nums[k])
                dp2[k] = min(dp2[k-1] * nums[k], nums[k])
            else:
                dp1[k] = max(dp2[k-1] * nums[k], nums[k])
                dp2[k] = min(dp1[k-1] * nums[k], nums[k])
        
        return max(dp1)