算法刷题目数组和矩阵
Source
Edit
History

子数组的最大累乘积

子数组的最大累乘积

一、题目

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

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

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

leetcode：https://leetcode.cn/problems/maximum-product-subarray/

二、思路

我们按照动态规划的思路来做，我们以 arr[i] 为底，有变量 max 表示 arr[0 ... i] 的最大值，变量 min 表示 arr[0 ... i] 的最小值。当我们遍历到 i+1 位置时，我们求以 i+1 为底的子数组的最大累乘积，所以一定要用到 arr[i+1] 这个值。

那么此时就有三个值来供我们判断

  • max * arr[i+1] 这个值，其中 max 表示 arr[0 ... i] 的最大累乘积。max * arr[i+1] 这个值可以参与评选当前以 i+1 为底的子数组的最大值。
  • min * arr[i+1] 这个值，其中 min 表示 arr[0 ... i] 的最小累乘积。min * arr[i+1] 这个值也可以参与评选当前以 i+1 为底的子数组的最大值。因为 min 如果为负数，且 arr[i+1] 也为负数，乘积可能更大。所以参与评选
  • arr[i+1] 这个值，因为我们求的是以 i+1 为底的子数组的最大累乘积，也就是 arr[i+1] 一定要使用。也有可能我们不使用 arr[0 ... i] 中的任何元素，而只使用 arr[i+1]，比如：[0.1, 0.1, 100] 在算到 100 的时候。

那么这三个值涵盖了我们想要的以 i+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
27
28
29
30
#include <vector>
#include <iostream>

class Solution {
public:
    double get_max_product(const std::vector<double>& arr) {
        if (arr.empty()) {
            return 0;
        }
        double max = arr[0];
        double min = arr[0];
        double res = max;
        for (int i = 1; i < arr.size(); ++i) {
            double first = max*arr[i];
            double second = min*arr[i];
            max = std::max(std::max(first, second), arr[i]);
            min = std::min(std::min(first, second), arr[i]);
            res = std::max(max, res);
        }
        return res;
    }
};

int main() {
    Solution s;
    std::vector<double> arr{2.5, 4, 0, 3, 0.5, 8, 01};
    auto res = s.get_max_product(arr);
    std::cout << res << std::endl;
    return 0;
}