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:
Input: nums = [2,3,-2,4] Output: 6 Explanation: [2,3] has the largest product 6.
Example 2:
Input: nums = [-2,0,-1] Output: 0 Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
Constraints:
1 <= nums.length <= 2 * 104-10 <= nums[i] <= 10- The product of any prefix or suffix of
numsis guaranteed to fit in a 32-bit integer.
Solution: Track high and low
Compute the low / high of prefix product, reset if nums[i] is higher than high or lower than low.
Swap low and high if nums[i] is a negative number.
e.g. [2, 3, -1, 8, -2]
nums[i] = 2, low = 2, high = 2
nums[i] = 3, low = 3, high = 2 * 3 = 6
nums[i] = -1, low = 6 * -1 = -6, high = -1
nums[i] = 8, low = -6 * 8 = -48, high = 8
nums[i] = -2, low = 8*-2 = -16, high = -48 * -2 = 96
Time complexity: O(n)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// Author: Huahua class Solution { public: int maxProduct(vector<int>& nums) { int ans = nums[0]; for (int i = 1, h = ans, l = ans; i < nums.size(); ++i) { if (nums[i] < 0) swap(l, h); l = min(nums[i], nums[i] * l); h = max(nums[i], nums[i] * h); ans = max(ans, h); } return ans; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment