前言
动态规划是面试中常考的知识点，特别是一些互联网大厂的面试，可以说必会考到一道涉及动态规划的算法题，因此掌握动态规划，能提高面试的通过率。
本文的内容为通过一道腾讯的面试题，即力扣 152. 乘积最大子数组，由暴力法求解一步一步演化到由动态规划进行求解来介绍动态规划。
题目
给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。
示例
解题思路
注意点
本题要求的是乘积最大的连续子数组而不是乘积最大的子序列，因此要求子数组中的元素在原数组中是连续的。
思考：整数数组可能存在的情况
由于题目已明确告知子数组中至少包含一个数字，因此主要存在以下两种情况：
-
整数数组 nums 中只包含一个元素；
-
整数数组 nums 中包含两个或两个以上元素。
思路
-
只包含一个元素，直接返回该元素；
-
包含两个或两个以上元素，暴力轮询或动态规划求乘积最大的连续子数组，返回乘积。
暴力法
初看该题，很容易想到可以通过暴力法去求解，即通过两层循环遍历整个数组。
Show me the Code
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22int maxProduct(vector<int>& nums) { int size = nums.size(); /* 整数数组 nums 只包含一个元素 */ if (size == 1) { return nums[0]; } /* maxRes 记录整数数组 nums 中乘积最大的连续子数组的乘积 */ int maxRes = nums[0]; for (int i = 0; i < size; ++i) { /* curMax 记录整数数组 nums 中当前乘积最大的连续子数组的乘积 */ int curMax = 1; for (int j = i; j < size; ++j) { curMax *= nums[j]; /* 不断更新 nums 中乘积最大的连续子数组的乘积 maxRes */ maxRes = max(maxRes, curMax); } } return maxRes; }
上面是通过暴力法去求解，由于进行了两层遍历，因此该解法的时间复杂度为O(n^2)，但由于未开辟额外的空间，所以空间复杂度为O(1)。但在面试过程中，如果提供这种解法，面试官往往会问还有没有更优的解法？也就是说面试官对当前的解法（时间复杂度过高）不太满意。
那有没有更优的解法呢？当然有！对动态规划有所了解的童鞋，在看到题目中的最大两个字，自然会想到通过动态规划去求解，因为涉及到求最优的问题，往往可以通过动态规划去解。
动态规划
由于整数数组 nums 中的元素可能有正数、负数和 0，因此连续子数组中的元素也可能是这三种情况。
如果连续子数组中的元素存在负数，正数乘以负数就成负数，那么最大值乘以负数就变成了最小值，因此需要同时考虑当前连续子数组乘积的最大值curMax和最小值curMin。
注意点
整数数组 nums 中存在负数，当遍历到以nums[i]（负数）结尾连续子数组时，需要交换 curMax 和 curMin。
举栗
以整数数组 nums = [2, 3, -2, 4] 为栗子，求乘积最大子数组的乘积。
如下图示：
Show me the Code
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25int maxProduct(vector<int>& nums) { int size = nums.size(); /* 整数数组 nums 只包含一个元素 */ if (size == 1) { return nums[0]; } /* curMax：以 nums[i] 结尾的当前乘积最大的连续子数组 */ /* curMin：以 nums[i] 结尾的当前乘积最小的连续子数组 */ int maxRes = nums[0], curMax = nums[0], curMin = nums[0]; for (int i = 1; i < size; ++i) { /* nums[i] < 0 时，交换 curMax 和 curMin */ if (nums[i] < 0) { swap(curMax, curMin); } /* 不断更新 curMax、curMin 和 maxRes */ curMax = max(curMax * nums[i], nums[i]); curMin = min(curMin * nums[i], nums[i]); maxRes = max(maxRes, curMax); } return maxRes; }
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24void swap(int *a, int *b) { int temp = *a; *a = *b; *b = temp; } int maxProduct(int* nums, int numsSize){ if (numsSize == 1) { return nums[0]; } int maxRes = nums[0], curMax = nums[0], curMin = nums[0]; for (int i = 1; i < numsSize; ++i) { if (nums[i] < 0) { swap(&curMax, &curMin); } curMax = fmax(curMax * nums[i], nums[i]); curMin = fmin(curMin * nums[i], nums[i]); maxRes = fmax(maxRes, curMax); } return maxRes; }
java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23int maxProduct(int[] nums) { int size = nums.length; if (size == 1) { return nums[0]; } int maxRes = nums[0], curMax = nums[0], curMin = nums[0]; for(int i = 1; i < size; ++i){ if(nums[i] < 0){ int tmp = curMax; curMax = curMin; curMin = tmp; } curMax = Math.max(curMax * nums[i], nums[i]); curMin = Math.min(curMin * nums[i], nums[i]); maxRes = Math.max(maxRes, curMax); } return maxRes; } }
python3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17class Solution: def maxProduct(self, nums: List[int]) -> int: size = len(nums) if size == 1: return nums[0] maxRes = curMax = curMin = nums[0] for i in range(1, size): if nums[i] < 0: curMax, curMin = curMin, curMax curMax = max(curMax * nums[i], nums[i]) curMin = min(curMin * nums[i], nums[i]) maxRes = max(maxRes, curMax) return maxRes
golang
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
31
32
33
34func maxProduct(nums []int) int { size := len(nums) if size == 1 { return nums[0] } maxRes, curMax, curMin := nums[0], nums[0], nums[0] for i := 1; i < size; i++ { if nums[i] < 0 { curMax, curMin = curMin, curMax } curMax = max(curMax * nums[i], nums[i]) curMin = min(curMin * nums[i], nums[i]) maxRes = max(curMax, maxRes) } return maxRes } func max(a, b int) int { if a > b { return a } return b } func min(a, b int) int { if a < b { return a } return b }
采用动态规划的方法去求解，由于只进行了一层遍历，因此其时间复杂度为O(n)，同样由于未开辟额外的空间，所以空间复杂度为O(1)。
往期动态规划相关精彩文章回顾
动态规划经典题之最长上升子序列最终版
动态规划经典题之最长上升子序列
到底是爬一阶还是爬两阶？
更多精彩
关注公众号【程序员小熊】
image
后台回复【算法】，即可获取高清无码的经典算法电子书~
后台回复【python】，即可获取高清无码的经典 python 电子书~
后台回复【1024】，即可获取三份来自 BAT 大佬的 Leetcode 刷题手册~
为了回馈读者，本公众号不定期会有送礼活动，敬请关注~
最后
以上就是年轻鱼最近收集整理的关于手撕腾讯面试题-乘积最大子数组的全部内容，更多相关手撕腾讯面试题-乘积最大子数组内容请搜索靠谱客的其他文章。
发表评论 取消回复