Keshawn_lu's Blog

Leetcode 152. 乘积最大子数组

字数统计: 331阅读时长: 1 min
2020/05/18 Share

题目简介:

给你一个整数数组 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;

}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: