Leetcode Blind 75 Practice-Maximum Product Subarray

Problem Statement

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.

Input: nums = [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.
Input: nums = [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

Solutions

  1. Dynamic programming — Store all calculating result, users can go back
class Solution:
def maxProduct(self, nums:List[int])->int:
tempProMax, tempProMin = [0 for _ in range(len(nums))], [0 for _ in range(len(nums))]
tempProMax[0] = tempProMin[0] = nums[0]
for i in range(1, len(nums)):
tempProMax[i] = max(tempProMax[i-1]*nums[i], tempProMin[i-1]*nums[i], nums[i])
tempProMin[i] = min(tempProMax[i-1]*nums[i], tempProMin[i-1]*nums[i], nums[i])
return max(tempProMax)

Complexity Analysis

Time Complexity: O(n)

class Solution:
def maxProduct(self, nums:List[int])->int:
max_so_far, min_so_far, max_global=nums[0],nums[0],nums[0]
for i in range(1, len(nums)):
max_so_far, min_so_far = max(max_so_far*nums[i], min_so_far*nums[i], nums[i]), min(max_so_far*nums[i], min_so_far*nums[i], nums[i])
max_global=max(max_so_far, max_global)
return max_global

Complexity Analysis

Time Complexity: O(1)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store