题目简介：
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例 1:
1
2
3
| 输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
|
示例 2:
1
2
3
| 输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
|
思路：
利用动态规划的思想，因为数组有负数的存在(存在负负得正为最大值的情况)，所以我们需要将每次以i为结尾的子数组乘积的最大值和最小值求出来。
最后将$f_{max}$的最大值求出即可。
代码如下：
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
| class Solution {
public:
int maxProduct(vector<int>& nums) {
int* dp_min = new int[nums.size()];
int* dp_max = new int[nums.size()];
dp_min[0] = nums[0];
dp_max[0] = nums[0];
int max_num = nums[0];
for(int i = 1; i < nums.size(); i++){
dp_max[i] = max(max(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]), nums[i]);
dp_min[i] = min(min(dp_max[i - 1] * nums[i], dp_min[i - 1] * nums[i]), nums[i]);
if(dp_max[i] > max_num)
max_num = dp_max[i];
}
return max_num;
}
};
|
