152. 乘积最大子数组

1. 背

乘法的特点是还有个负负得正，加法是没有这个问题的。所以的在做的时候要弄两个dp数组，一个用来记录最大的数字，一个用来记录最小的数字，完了取个三个数字的max

2. 题目

给你一个整数数组 nums ，请你找出数组中乘积最大的非空连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

测试用例的答案是一个 32-位 整数。

子数组 是数组的连续子序列。

示例 1:

输入: nums = [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
示例 2:

输入: nums = [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-product-subarray
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

3. 答案

#include 

using namespace std;
int maxProduct(const vector& nums) {
  int n = static_cast(nums.size());
  if (1 == n) return nums[0];
  vector maxx(n);
  vector minn(n);
  maxx[0] = nums[0];
  minn[0] = nums[0];
  for (int i = 1; i < n; ++i) {
    maxx[i] = max(max(maxx[i - 1] * nums[i], minn[i - 1] * nums[i]), nums[i]);
    minn[i] = min(min(maxx[i - 1] * nums[i], minn[i - 1] * nums[i]), nums[i]);
  }
  return *max_element(maxx.begin(), maxx.end());
}
int main() {
  cout << maxProduct({2, 3, -2, 4}) << endl;
  return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21