LeetCode 152. 乘积最大子数组
题目描述
思路分析
方案一：动态规划
这道题的关键在于，由于负数的存在，最大值可能来自最小值与一个负数相乘而来。因此我们在遍历时，需要同时记录以当前位置结尾的最大乘积和最小乘积。
方案二：前后遍历乘积
从左到右遍历一遍，再从右到左遍历一遍，每次记录乘积并更新最大值。因为负数个数为偶数时乘积可以为正，因此前后都要遍历。
参考代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxProduct(nums []int) int {
n := len(nums)
maxF := make([]int, n)
minF := make([]int, n)
maxF[0], minF[0] = nums[0], nums[0]
res := nums[0]
for i := 1; i < n; i++ {
maxF[i] = max(nums[i], maxF[i-1]*nums[i], minF[i-1]*nums[i])
minF[i] = min(nums[i], maxF[i-1]*nums[i], minF[i-1]*nums[i])
res = max(res, maxF[i])
}
return res
}
- 时间复杂度：O(n)
- 空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func maxProduct(nums []int) int {
curMax, curMin := nums[0], nums[0]
res := nums[0]
for i := 1; i < len(nums); i++ {
if nums[i] < 0 {
curMax, curMin = curMin, curMax
}
curMax = max(nums[i], curMax*nums[i])
curMin = min(nums[i], curMin*nums[i])
res = max(res, curMax)
}
return res
}
- 时间复杂度：O(n)
- 空间复杂度：O(1)
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
26
func maxProduct(nums []int) int {
n := len(nums)
res := nums[0]
cur := 1
// 从左到右遍历
for i := 0; i < n; i++ {
if cur == 0 {
cur = 1
}
cur *= nums[i]
res = max(res, cur)
}
cur = 1
// 从右到左遍历
for i := n - 1; i >= 0; i-- {
if cur == 0 {
cur = 1
}
cur *= nums[i]
res = max(res, cur)
}
return res
}
- 时间复杂度：O(n)，分别正反各遍历一次。
- 空间复杂度：O(1)，只使用了常数级变量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int maxProduct(int[] nums) {
int maxP = nums[0], minP = nums[0];
int res = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] < 0) {
int temp = maxP;
maxP = minP;
minP = temp;
}
maxP = Math.max(nums[i], maxP * nums[i]);
minP = Math.min(nums[i], minP * nums[i]);
res = Math.max(res, maxP);
}
return res;
}
}
本博客所有文章除特别声明外，均采用
CC BY-NC-SA 4.0
许可协议，转载请注明出处！