Leetcode152 Maximum Product Subarray python

题目

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.
Example 1:
Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Example 2:
Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

解法1：brutal force

利用双层循环进行暴力求解，但是用python的话会TLE，但是用C++貌似brutal force可以过

class Solution(object):
def maxProduct(self, nums):
""":type nums: List[int]:rtype: int"""final_ans = -float('inf')n = len(nums)if n == 1:return nums[0]for i in range(n):curr_ans = 1for j in range(n-i):curr_ans*=nums[i+j]final_ans = max(curr_ans,final_ans)return final_ans

解法2：同时记录最小和最大值

通过两个数组同时记录在某个位置时的当前最大值和最小值，用positive和negative代表
当前的最大值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最大值。
当前的最小值等于已知的最大值、最小值和当前值的乘积，当前值，这三个数的最小值。
结果是最大值数组中的最大值

class Solution(object):
def maxProduct(self, nums):
""":type nums: List[int]:rtype: int"""n = len(nums)positive = [0]*len(nums)negative = [0]*len(nums)positive[0],negative[0],ans = nums[0],nums[0],nums[0]for i in range(1,n):positive[i] = max(positive[i-1]*nums[i],negative[i-1]*nums[i],nums[i])negative[i] = min(positive[i-1]*nums[i],negative[i-1]*nums[i],nums[i])ans = max(ans,positive[i])return ans

时间复杂度：O(N)
空间复杂度：O(N)

解法3：分类讨论

对于当前所在元素按照正负情况进行分类讨论，同样需要同时记录最大值和最小值，这种方法时间复杂度与方法2相同，空间复杂度将为O(1)
如果当前元素为正，则当前最大值为当前元素与之前最大值的乘积，当前最小值为当前元素与之前最小值的乘积
如果当前元素为负，则当前最大值为当前元素与之前最小值的乘积，当前最小值为当前元素与之前最大值的乘积
最终结果为当前最大元素和之前保存临时结果的最大值

class Solution(object):def maxProduct(self, nums):""":type nums: List[int]:rtype: int"""curr_min = curr_max = ans = nums[0]for i in range(1,len(nums)):if nums[i]>=0:curr_min,curr_max=min(nums[i],nums[i]*curr_min),max(nums[i],nums[i]*curr_max)   else:curr_min,curr_max=min(nums[i],nums[i]*curr_max),max(nums[i],nums[i]*curr_min) ans = max(ans,curr_max)return ans

时间复杂度：O(N)
空间复杂度：O(1)

解法4：双向动规

从两边分别记录从两个方向的最大值，a or 1起到的作用是，如果a是0，则取nums[i]，否则与之前的a进行累乘，最大值为从两个方向获取的最大值中的最大值

class Solution(object):def maxProduct(self, nums):""":type nums: List[int]:rtype: int"""prefix, suffix, max_so_far = 0, 0, float('-inf')for i in range(len(nums)):prefix = (prefix or 1) * nums[i]suffix = (suffix or 1) * nums[-i-1]max_so_far = max(max_so_far, prefix, suffix)return max_so_far

时间复杂度：O(N)
空间复杂度：O(1)