https://leetcode.com/problems/maximum-product-subarray/
Medium
问题描述：
Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
1
2
3
| Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
|
Example 2:
1
2
3
| Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.
|
思路及代码：
这一题要求连续子串的最大乘积。
一开始我想暴力求解这个问题，也就是将所有的子串乘积算出来，再比较就完事了，然而暴力求解的后果只有一个，就是TLE，显然不可行。
我们可以换个角度想这个问题，想要找到有最大乘积的子串，我们首先考虑对乘积影响最大的因素，乘积和求和不同，如果遇到0或是负数，最大乘积就可能从最大变成最小，而最小乘积反而变成最大。因此，我们需要同时记录当前的最大乘积和最小乘积。
i位置的最大乘积应该由三个因素决定，分别是当前最大乘积current_max[i]、当前最小乘积current_min[i]以及该位置的数nums[i]。
代码如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| def maxProduct(nums):
if len(nums) == 1:
return nums[0]
current_max = [0] * len(nums)
current_min = [0] * len(nums)
res = current_max[0] = current_min[0] = nums[0]
for i in range(1, len(nums)):
current_max[i] = max(current_max[i - 1] * nums[i], current_min[i - 1] * nums[i], nums[i])
current_min[i] = min(current_min[i - 1] * nums[i], current_max[i - 1] * nums[i], nums[i])
res = max(res, current_max[i])
return res
|
我们还可以进一步的改进代码，降低空间复杂度。通过考虑当前nums[i]的正负情况，提前交换当前的最大最小乘积：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| def maxProduct(nums):
if len(nums) == 1: return nums[0]
current_max = current_min = res = nums[0]
for i in range(1, len(nums)):
if nums[i] < 0:
current_max, current_min = current_min, current_max
current_max = max(current_max * nums[i], nums[i])
current_min = min(current_min * nums[i], nums[i])
res = max(current_max, res)
return res
|