152. Maximum Product Subarray
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) -> O(1) class Solution: def maxProduct(self, nums: List[int]) -> int: @cache def dp(i: int) -> Tuple[int, int]: """min / max subarray product ends with nums[i].""" if i == 0: return nums[i], nums[i] low, hi = dp(i - 1) if nums[i] < 0: low, hi = hi, low return min(low * nums[i], nums[i]), max(hi * nums[i], nums[i]) return max(dp(i)[1] for i in range(len(nums))) |
1567. Maximum Length of Subarray With Positive Product
Python3
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
# Author: Huahua # Time complexity: O(n) # Space complexity: O(n) -> O(1) class Solution: def getMaxLen(self, nums: List[int]) -> int: @cache def dp(i: int) -> Tuple[int, int]: """Max length of pos/neg product ends with nums[i].""" if i < 0 or nums[i] == 0: return 0, 0 p, n = dp(i - 1) if nums[i] > 0: return p + 1, n + 1 if n else 0 else: # nums[i] < 0 return n + 1 if n else 0, p + 1 return max(dp(i)[0] for i in range(len(nums))) |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment