如果你想在校招中顺利拿到更好的offer,阿秀建议你多看看前人的经验 ,比如准备简历实习上岸经历校招总结阿里、字节、腾讯、美团等一二线大厂真实面经也欢迎来一起参加秋招打卡活动 等;如果你是计算机小白,学习/转行/校招路上感到迷茫或者需要帮助,可以点此联系阿秀;免费分享阿秀个人学习计算机以来的收集到的好资源,点此白嫖;如果你需要《阿秀的学习笔记》网站中求职相关知识点的PDF版本的话,可以点此下载

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

力扣原题链接(点我直达) (opens new window)

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

示例 1:

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

示例 2:

输入: [-2,0,-1]
输出: 0
解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。
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;
    }
1
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;



}
1
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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17