【LeetCode】乘積最大子數組

總結

• 善于變通
• 文章來源：LawsonAbs
• 待更新~

想法

想法一

01.改變正負号。如果是偶數個，則符号全部變正。

02.根據改變後的符号再來求最大積。

這種方法是有問題的：

[-1,-4,-3] 在遇到這種樣例的時候，數組會變成 [1,4,-3] 這樣，而不是[-1,4,3] ，然而後者才是正确的答案。

# class Solution:
#     def maxProduct(self, nums: List[int]) -> int:    
#         pre_idx = None
#         cnt = 0
#         for i in range(len(nums)):
#             if nums[i] < 0 : # 如果目前的值小于0
#                 if pre_idx is None:
#                     pre_idx = i
#                 cnt += 1
#             elif nums[i] == 0: # 重置
#                 cnt = 0
#                 pre_idx = None
#             if cnt % 2 == 0 and cnt: # 已經有連續兩個負号
#                 nums[pre_idx] *= -1
#                 nums[i] *=  -1 # 改符号
#                 pre_idx = None
#                 cnt = 0
        
#         # product = copy(nums)
#         print(nums)
#         max_val = 0
#         whole = 0
#         for i in range(1,len(nums)):
#             if nums[i] > 0 and nums[i-1] > 0:
#                 nums[i] = nums[i-1] * nums[i]
#                 whole += 1
#             max_val = max(max_val,nums[i])
#         if whole == len(nums): # 如果是全部數字都算進去了
#             pass
#         print(nums)
#         print(max_val)      

想法二

from typing import List
from copy import copy

class Solution():
    def maxProduct(self, nums: List[int]) -> int:    
        dp_min = copy(nums) # 第i項的最小值
        dp_max = copy(nums) # 第i項的最大值
        total = nums[0]
        for i in range(1,len(nums)):
            total *= nums[i]
            dp_min[i] = min(dp_min[i-1]*nums[i],dp_max[i-1]*nums[i],nums[i])
            dp_max[i] = max(dp_min[i-1]*nums[i],dp_max[i-1]*nums[i],nums[i])
        # print(dp_max)
        res =  max(dp_max)
        return res
    

s = Solution()
nums = [-2,3,-2,4,-1,0,0,-4]
# nums = [-2,-1,-3,-4] # 得到的結果應該是12
# nums = [-1,-4,-3]
nums = [-2,-3,1] # 會計算整個數組的乘積
# nums = [-6,-2,-3,4,-5]
# nums = [-6,-2,-3,4]
# nums = [   -2,-3,4,-5]

out = s.maxProduct(nums)
print(out)