152. Maximum Product Subarray
Medium
Given an integer array
nums, find a subarray that has the largest product, and return the product.
The test cases are generated so that the answer will fit in a 32-bit integer.
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.
使用兩個陣列儲存當前包含前一個元素的最大 / 最小子數列。
最大可能是 目前的單個元素、最大子數列*當前元素(若當前元素為正數)、最小子數列*當前元素(若當前元素為負數)
Runtime: 4 ms, faster than 93.98%
Memory Usage: 6.7 MB, less than 6.54%
func maxProduct(nums []int) int {
// min := nums[0]
res := nums[0]
dp1 := []int{nums[0]}
dp2 := []int{nums[0]}
for i:=1; i<len(nums); i++ {
dp1 = append(dp1, max(nums[i], dp1[i - 1] * nums[i], dp2[i - 1]* nums[i]))
dp2 = append(dp2, min(nums[i], dp2[i - 1] * nums[i], dp1[i - 1]* nums[i]))
if dp1[i] > res {
res = dp1[i]
}
}
return res
}
func max(a, b, c int) int {
if a >= b && a >= c {
return a
} else if b >= a && b >= c{
return b
}
return c
}
func min(a, b, c int) int {
if a <= b && a <= c {
return a
} else if b <= a && b <= c{
return b
}
return c
}
Runtime: 4 ms, faster than 93.98%
Memory Usage: 3.3 MB, less than 100%
func maxProduct(nums []int) int {
res := nums[0]
maxx := nums[0]
minn := nums[0]
for i:=1; i<len(nums); i++ {
premax := maxx
maxx = max(nums[i], maxx * nums[i], minn* nums[i])
minn = min(nums[i], minn * nums[i], premax* nums[i])
if maxx > res {
res = maxx
}
}
return res
}
func max(a, b, c int) int {
if a >= b && a >= c {
return a
} else if b >= a && b >= c{
return b
}
return c
}
func min(a, b, c int) int {
if a <= b && a <= c {
return a
} else if b <= a && b <= c{
return b
}
return c
}