题目描述
给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
测试用例的答案是一个 32 - 位 整数。
子数组 是数组的连续子序列。
示例 1:
- 输入: nums = [2,3,-2,4]
- 输出:
6
- 解释: 子数组 [2,3] 有最大乘积 6。
示例 2:
- 输入: nums = [-2,0,-1]
- 输出: 0
- 解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
提示:
- 1 <= nums.length <= 2 * 104
-10 <= nums[i] <= 10nums 的任何前缀或后缀的乘积都 保证 是一个 32 - 位 整数
解法一：动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
func minMax(nums ...int) (int, int) {
min, max := nums[0], nums[0]
for _, val := range nums {
if val > max {
max = val
}
if val < min {
min = val
}
}
return min, max
}
func maxProduct(nums []int) int {
n := len(nums)
minVal, maxVal := nums[0], nums[0]
ans := nums[0]
for i := 1; i < n; i++ {
minVal, maxVal = minMax(minVal*nums[i], maxVal*nums[i], nums[i])
if ans < maxVal {
ans = maxVal
}
}
return ans
}
|
