这是四则或许对你有帮助的讯息
1、👉 最近我发现了一个每日都会推送最新校招资讯的《校招日程》文档，其中包括往届补录、应届实习校招信息,比如各种大厂、国企、银行、事业编等信息都会定期更新，帮忙扩散一下。
2、😍 免费分享阿秀个人学习计算机以来的收集到的免费资源，点此白嫖。
3、🚀如果你想在校招中顺利拿到更好的offer，阿秀建议你多看看前人踩过的坑和留下的经验，事实上你现在遇到的大多数问题你的学长学姐师兄师姐基本都已经遇到过了。
4、🔥 欢迎准备计算机校招的小伙伴加入我的学习圈子，一个人踽踽独行真的不如一群人报团取暖，过去22届和23届的小伙伴好好跟着走下去的，最后基本都拿到了不错的offer！如果你需要《阿秀的学习笔记》网站中📚︎校招八股文相关知识点的PDF版本的话，可以点此下载 。
# 152. 乘积最大子序列 同样经典的问题
力扣原题链接（点我直达） (opens new window)
给定一个整数数组 nums ，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。
示例 1:
输入: [2,3,-2,4]
输出: 6
解释: 子数组 [2,3] 有最大乘积 6。
2
3
示例 2:
输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
2
3
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%的用户
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;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 第二版，动态规划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%的用户
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;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 精简版
执行用时 :4 ms, 在所有 cpp 提交中击败了93.25%的用户
内存消耗 :8.9 MB, 在所有 cpp 提交中击败了89.24%的用户
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;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17