12/19/2022 Two Leetcode Problems

[box-lin]

• 238. Product of Array Except Self
• 152. Maximum Product Subarray

Instruction:

• Participant please comment with your solutions provided with your explanation below! Go leetcode.

[137thphxx]

238. multiply from left then from right except it self

     class Solution:
     def productExceptSelf(self, nums: List[int]) -> List[int]:
         length = len(nums)
         answer = [1] * length
         for i in range(1, length):
             answer[i] = answer[i-1]*nums[i-1]
     
         temp = 1
         for i in range(length-1, -1, -1):
             answer[i] = answer[i]*temp
             temp = temp * nums[i]
         return answer

239. 超时

     class Solution:
     def maxProduct(self, nums: List[int]) -> int:
         length = len(nums)
         max_num = max(nums)
         sortlist = [[]]
     
         for i in range(length + 1):
             for j in range(i):
                 sortlist.append(nums[j:i])
     
         get = len(sortlist)
         for k in range(1, get):
             temp = prod(sortlist[k])
             if temp > max_num:
                 max_num = temp
     
         return max_num

     class Solution:
     def maxProduct(self, nums: List[int]) -> int:
         max_prod, min_prod, ans = nums[0], nums[0], nums[0]
         for i in range(1, len(nums)):
             x = max(nums[i], max_prod*nums[i], min_prod*nums[i])
             y = min(nums[i], max_prod*nums[i], min_prod*nums[i])            
             max_prod, min_prod = x, y
             ans = max(max_prod, ans)
         return ans

[box-lin]

# Question 238 
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # ans is a pre-product except itself from left to right 
        ans = [] 
        p = 1 
        for num in nums:
            ans.append(p)
            p *= num 

        # ans is now a pre-product * post-product except itself.
        posp = 1
        for i in range( len(nums)-1, -1, -1):
            ans[i] *= posp
            posp *= nums[i]
        return ans

# Question 152
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        # the idea is to keep max and min dp as well, since we have negative number.
        n = len(nums)
        maxdp, mindp = [0]*n, [0]*n
        for i in range(n):
            if i == 0:
                maxdp[i] = nums[i]
                mindp[i] = nums[i]
            else:
                maxdp[i] = max(maxdp[i-1]*nums[i], mindp[i-1]*nums[i], nums[i])
                mindp[i] = min(maxdp[i-1]*nums[i], mindp[i-1]*nums[i], nums[i])

        return max(maxdp)