This is a place to put my clutters, no matter you like it or not, welcome here.
0%
152. Maximum Product Subarray
Posted onEdited onIn面試Views: Symbols count in article: 726Reading time ≈1 mins.
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
It is guaranteed that the answer will fit in a 32-bit integer.
A subarray is a contiguous subsequence of the array.
Example 1:
1 2 3
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
Example 2:
1 2 3
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
邊走邊找看過最大乘積。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
# TC:O(n), TS:O(1)
class Solution: def maxProduct(self, nums: List[int]) -> int: res = max(nums) curMin, curMax = 1, 1 for n in nums: if n == 0: curMin, curMax = 1, 1 continue temp = curMax * n curMax = max(n, n * curMin, n * curMax) curMin = min(n, n * curMin, temp) res = max(res, curMax) return res