跳转至

152. 乘积最大子序列

这是六则或许对你有些许帮助的信息:

⭐️1、阿秀与朋友合作开发了一个编程资源网站，目前已经收录了很多不错的学习资源和黑科技（附带下载地址），如过你想要寻求合适的编程资源，欢迎体验以及推荐自己认为不错的资源，众人拾柴火焰高，我为人人，人人为我🔥！

2、👉23年5月份阿秀从字节跳动离职跳槽到某外企期间，为方便自己找工作，增加上岸几率，我自己从0开发了一个互联网中大厂面试真题解析网站，包括两个前端和一个后端。能够定向查看某些公司的某些岗位面试真题，比如我想查一下行业为互联网，公司为字节跳动，考察岗位为后端，考察时间为最近一年之类的面试题有哪些？

网站地址：InterviewGuide大厂面试真题解析网站。点此可以查看该网站的视频介绍：B站视频讲解 如果可以的话求个B站三连，感谢！

3、😊 分享一个阿秀自己私藏的黑科技网站，点此直达，主要是各类小众实用APP、网站等，除此外也包括高清影视、音乐、电视剧、AI、纪录片、英语四六级考试、考研考公、副业等资源。

4、😍免费分享阿秀个人学习计算机以来收集到的免费学习资源，点此白嫖；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏；也记录一下自己以前买过的不错的计算机书籍、网络专栏和垃圾付费专栏

5、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。

6、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行不如一群人报团取暖，圈子里沉淀了很多过去21/22/23/24/25届学长学姐的经验和总结，好好跟着走下去的，最后基本都可以拿到不错的offer！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。

152. 乘积最大子序列 同样经典的问题

力扣原题链接（点我直达）

给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。

示例 1:

Text Only
1
2
3
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

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

https://leetcode-cn.com/problems/maximum-product-subarray/solution/xiang-xi-tong-su-de-si-lu-fen-xi-duo-jie-fa-by--36/

解法一 分段法

给乘积带来问题的是0和负数。

1，用0将序列分割成不再包含0的段。每个段中的最大值，再与0比较取最大值。

例如：[2,3,0,4]

分成两段。[2,3],[4]。段内最大值为6，4。与0比较。整个序列的最大值为6

例如：[2,-3,0,-4]

分成两段。[2,-3],[-4]。段内最大值为2，-4。与0比较。整个序列的最大值为2

2，负数的个数很关键。如果有偶数个负数，负数相乘为正数，那么全部乘积应该是最大的。

如果有奇数个负数，那么用第一个奇数A将序列分成两段。两段中的最大值，再与A比较取最大值。

另外， 用最后一个奇数B将序列分成两段。两段中的最大值，再与B比较取最大值。

例如：[2,3,-2,4] -2将序列分成两段。[2,3]和[4]。两段的最大值为6和4.

例如：[3,-2,-3,-3,1,3,0]

-2将序列分成两段。 [3]和[ -3,-3,1,3,0 ]。最大值为3和27.最大值为27.

最后一个-3，将序列分成两段。 [3,-2,-3 ]和[ 1,3,0 ]。最大值为18和3. 最大值为18.

最终最大值为27.

关键是用方便的方法指出第一个和最后一个负数。

从左向右累乘，当到最后一个负数时，左边的偶数个负数都乘过了。乘上此负数，值就变成负数了。最大值显然是左边的最大值。

从右向左累乘，当到最后一个负数时，右边的偶数个负数都乘过了。乘上此负数，值就变成负数了。最大值显然是右边的最大值。

执行用时 :8 ms, 在所有 cpp 提交中击败了64.69%的用户

内存消耗 :9.1 MB, 在所有 cpp 提交中击败了32.52%的用户

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
    int maxProduct(vector<int>& nums) {
    int res = nums[0];
    int left_max = 1;
    for (auto &a:nums) {
        left_max *= a;
        if(left_max>res) res = left_max;
        if(left_max == 0) left_max=1;
    }
    int right_max = 1;
    for (int i = nums.size() - 1; i >= 0; --i) {
        right_max *= nums[i];
        if (right_max > res) res = right_max;
        if (right_max == 0) right_max = 1;
    }
    return res;
    }

第二版，动态规划DP

解法二 动态规划 设d[i]表示以A[i]为结尾的乘积最大值。

设e[i]表示以A[i]为结尾的乘积最小值。

当A[i] >=0 且 d[i-1]>=0时，d[i]=A[i]*d[i-1]。

当A[i] >=0 且 d[i-1] < 0时，d[i]=A[i]。

当A[i] <0 且 e[i-1] <0 时，d[i]=A[i] * e[i-1]。

当 A[i]<0 且 e[i-1] >= 0 时，d[i]=A[i] 。

d[i]=max( A[i]*d[i-1] ， A[i] ， A[i] * e[i-1] )。

用同样的方法求e.

当A[i] >=0 且 e[i-1]>=0时，e[i]=A[i]。

当A[i] >=0 且 e[i-1] < 0时，e[i]=A[i]*e[i-1]。

当A[i] <0 且 d[i-1] <0 时，e[i]=A[i]。

当 A[i]<0 且 d[i-1] >= 0 时，e[i]=A[i]*d[i-1] 。

e[i]=max( A[i]*d[i-1] ， A[i] ， A[i] * e[i-1] )。

执行用时 :8 ms, 在所有 cpp 提交中击败了64.69%的用户

内存消耗 :9.2 MB, 在所有 cpp 提交中击败了22.62%的用户

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
int maxProduct(vector<int>& nums) {

    int N = nums.size();
    vector<int> d(N), e(N);
    d[0] = nums[0];
    e[0] = nums[0];
    int ans = INT_MIN;
    ans = max(ans, max(d[0], e[0]));
    for (int i = 1; i < N; ++i) {
        d[i] = max(nums[i], max(nums[i] * d[i - 1], nums[i] * e[i - 1]));
        e[i] = min(nums[i], min(nums[i] * d[i - 1], nums[i] * e[i - 1]));
        ans = max(ans, max(d[i], e[i]));
    }
    return ans;



}

精简版

执行用时 :4 ms, 在所有 cpp 提交中击败了93.25%的用户

内存消耗 :8.9 MB, 在所有 cpp 提交中击败了89.24%的用户

C++
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
    int maxProduct(vector<int>& nums) {
    int n = nums.size();
    if (n == 0) {
        return 0;
    }
    int dpMax = nums[0];
    int dpMin = nums[0];
    int maxNum = nums[0];
    for (int i = 1; i < n; i++) {
        //更新 dpMin 的时候需要 dpMax 之前的信息，所以先保存起来
        int preMax = dpMax;
        dpMax = max(dpMin * nums[i], max(dpMax * nums[i], nums[i]));
        dpMin = min(dpMin * nums[i], min(preMax * nums[i], nums[i]));
        maxNum = max(maxNum, dpMax);
    }
    return maxNum;
    }