手撕腾讯面试题-乘积最大子数组

前言

动态规划是面试中常考的知识点,特别是一些互联网大厂的面试,可以说必会考到一道涉及动态规划的算法题,因此掌握动态规划,能提高面试的通过率。

本文的内容为通过一道腾讯的面试题,即力扣 152. 乘积最大子数组,由暴力法求解一步一步演化到由动态规划进行求解来介绍动态规划

题目

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

手撕腾讯面试题-乘积最大子数组示例

解题思路

注意点

本题要求的是乘积最大的连续子数组而不是乘积最大的子序列,因此要求子数组中的元素在原数组中是连续的

思考:整数数组可能存在的情况

由于题目已明确告知子数组中至少包含一个数字,因此主要存在以下两种情况:

  1. 整数数组 nums 中只包含一个元素;
  2. 整数数组 nums 中包含两个或两个以上元素。

思路

  • 只包含一个元素,直接返回该元素;
  • 包含两个或两个以上元素,暴力轮询或动态规划求乘积最大的连续子数组,返回乘积。

暴力法

初看该题,很容易想到可以通过暴力法去求解,即通过两层循环遍历整个数组。

Show me the Code

C++

手撕腾讯面试题-乘积最大子数组
 1 int maxProduct(vector<int>& nums) {
 2     int size = nums.size();
 3     /* 整数数组 nums 只包含一个元素 */
 4     if (size == 1) {
 5         return nums[0];
 6     }
 7 
 8     /* maxRes 记录整数数组 nums 中乘积最大的连续子数组的乘积 */
 9     int maxRes = nums[0];
10     for (int i = 0; i < size; ++i) {
11         /* curMax 记录整数数组 nums 中当前乘积最大的连续子数组的乘积 */
12         int curMax = 1;
13         for (int j = i; j < size; ++j) {
14             curMax *= nums[j];
15             /* 不断更新 nums 中乘积最大的连续子数组的乘积 maxRes */
16             maxRes = max(maxRes, curMax);
17         }
18     }
19     
20     return maxRes;
21 }
View Code

 

上面是通过暴力法去求解,由于进行了两层遍历,因此该解法的时间复杂度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 int maxProduct(vector<int>& nums) {
 2     int size = nums.size();
 3     /* 整数数组 nums 只包含一个元素 */
 4     if (size == 1) {
 5         return nums[0];
 6     }
 7 
 8     /* curMax:以 nums[i] 结尾的当前乘积最大的连续子数组 */
 9     /* curMin:以 nums[i] 结尾的当前乘积最小的连续子数组 */
10     int maxRes = nums[0], curMax = nums[0], curMin = nums[0];
11     for (int i = 1; i < size; ++i) {
12         /* nums[i] < 0 时,交换 curMax 和 curMin */
13         if (nums[i] < 0) {
14             swap(curMax, curMin);
15         }
16         
17         /* 不断更新 curMax、curMin 和 maxRes */
18         curMax = max(curMax * nums[i], nums[i]);
19         curMin = min(curMin * nums[i], nums[i]);
20         maxRes = max(maxRes, curMax);
21     }
22     
23     return maxRes;
24 }
View Code

 

C

手撕腾讯面试题-乘积最大子数组
 1 void swap(int *a, int *b) {
 2     int temp = *a;
 3     *a = *b;
 4     *b = temp;
 5 }
 6 int maxProduct(int* nums, int numsSize){
 7     if (numsSize == 1) {
 8         return nums[0];
 9     }
10 
11     int maxRes = nums[0], curMax = nums[0], curMin = nums[0];
12     for (int i = 1; i < numsSize; ++i) {
13         if (nums[i] < 0) {
14             swap(&curMax, &curMin);
15         }
16         
17         curMax = fmax(curMax * nums[i], nums[i]);
18         curMin = fmin(curMin * nums[i], nums[i]);
19         maxRes = fmax(maxRes, curMax);
20     }
21     
22     return maxRes;
23 }
View Code

 

java

手撕腾讯面试题-乘积最大子数组
 1 int maxProduct(int[] nums) {
 2         int size = nums.length;
 3         if (size == 1) {
 4             return nums[0];
 5         }
 6 
 7         int maxRes = nums[0], curMax = nums[0], curMin = nums[0];
 8         for(int i = 1; i < size; ++​i){
 9             if(nums[i] < 0){ 
10               int tmp = curMax;
11               curMax = curMin;
12               curMin = tmp;
13             }
14 
15             curMax = Math.max(curMax * nums[i], nums[i]);
16             curMin = Math.min(curMin * nums[i], nums[i]);
17             maxRes = Math.max(maxRes, curMax);
18         }
19         
20         return maxRes;
21     }
22 }
View Code

 

python3

手撕腾讯面试题-乘积最大子数组
 1 class Solution:
 2     def maxProduct(self, nums: List[int]) -> int:
 3         size = len(nums)
 4         if size == 1:
 5             return nums[0]
 6         
 7         maxRes = curMax = curMin = nums[0]
 8         for i in range(1, size):
 9             if nums[i] < 0:
10                 curMax, curMin = curMin, curMax
11 
12             curMax = max(curMax * nums[i], nums[i])
13             curMin = min(curMin * nums[i], nums[i])
14             maxRes = max(maxRes, curMax)
15 
16         return maxRes
View Code
 

golang

手撕腾讯面试题-乘积最大子数组
 1 func maxProduct(nums []int) int {
 2     size := len(nums)
 3     if size == 1 {
 4         return nums[0]
 5     }
 6 
 7     maxRes, curMax, curMin := nums[0], nums[0], nums[0]
 8     for i := 1; i < size; i++ {
 9         if nums[i] < 0 {
10             curMax, curMin = curMin, curMax
11         }
12         
13         curMax = max(curMax * nums[i], nums[i])
14         curMin = min(curMin * nums[i], nums[i])
15         maxRes = max(curMax, maxRes)
16     }
17 
18     return maxRes
19 }
20 
21 func max(a, b int) int {
22     if a > b {
23         return a
24     }
25     return b
26 }
27 
28 func min(a, b int) int {
29     if a < b {
30         return a
31     }
32     return b
33 }
View Code
 

采用动态规划的方法去求解,由于只进行了一层遍历,因此其时间复杂度O(n),同样由于未开辟额外的空间,所以空间复杂度O(1)

 

上一篇:【每日Leetcode-第三天】无重复字符的最长子串


下一篇:LC1043. Partition Array for Maximum Sum