LeetCode 152 Maximum Product Subarray

LeetCode

Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.

The test cases are generated so that the answer will fit in a 32-bit integer.

A subarray is a contiguous subsequence of the array.

Example 1:

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Constraints:

`1 <= nums.length <= 2 10<sup>4</sup>*-10 <= nums[i] <= 10* The product of any prefix or suffix ofnums` is guaranteed to fit in a 32-bit integer.

题目大意：

求子数组最大积

解题思路：

类似于LeetCode 053 Maximum Subarray求子数组最大和，用DP。

递归式； dp为以某个数为结尾的最大子数组积，dp2为以某个数为结尾的最小子数组积

dp[i] = max(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
dp2[i] = min(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])

解题步骤：

N/A

注意事项：

1. 由于负负得正，所以是多状态DP。需要同时赋值

Python代码：

# dp[i] = max(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
# dp2[i] = min(num[i], dp[i-1] * num[i], dp2[i-1] * num[i])
def maxProduct(self, nums: List[int]) -> int:
	max_p, min_p, res = 1, 1, float('-inf')
	for n in nums:
		# remember assign same time
		max_p, min_p = max(n, max_p * n, min_p * n), min(n, max_p * n, min_p * n) # 4, -48 | 4, -8, -48
		res = max(res, max_p) # 6
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(1)