【LeetCode】Maximum Product Subarray 解法【Python】

leetcode.com

Maximum Subarrayの総乗バージョン。

しかし、解法が全然違う（自分が思いついた解法は）。

総和の場合と同じように、スプレッドシートで計算する。

ここから見えてきたものをルール化する。

inputの配列の内、最大になる候補を「特定範囲」とすると。

• 特定範囲に0がはいると総乗は0
• 特定範囲に負が奇数個入ると、総乗は負
• 特定範囲に負が偶数個入ると、総乗は正

これらを踏まえてロジックは下記のようにする。

• 配列内に0が出てくるまでの範囲を特定配列とする
• 特定範囲に負が偶数個の場合は、特定範囲の総乗を最大値候補にする
• 特定範囲に負が奇数個の場合は、先頭の負を除く範囲での総乗と、最後尾の負を除く範囲での総乗を比較し、大きい方法を最大値候補にする
• 最大値候補から、最も大きい値を返却する

ソースは汚いのでいつかのタイミングで修正したい。

def prod(nums):
    if len(nums) == 0:
        return None
    
    result = nums[0]
    for num in nums[1:]:
        result *= num
    return result
        

class Solution:
    
        
        
    def maxProduct(self, nums: List[int]) -> int:
        """
        負を偶数個含むなら、最大になる
        負を奇数個含むなら、最小になる
        0を含むとかならず0
        
        0がある場合は,0で区切る
        その範囲で、
        負が偶数個の範囲が、ローカルマックス
        左右のどっちを削れば、最大になるか。
        １つだけならそれ正だろうが負だろうが
        """
        if len(nums) == 1:
            return nums[0]
        
        local_nums=[]
        max_ = nums[0]
        count_minus = 0
        local_sumproduct = 1
        local_minus_idx_l = -1
        local_minus_idx_r = -1
        zero_idx_l = -1
        zero_idx_r = -1
        for idx, num in enumerate(nums):
            
            if num != 0:
                local_sumproduct *= num
                if num < 0:
                    count_minus += 1
                    
                    if local_minus_idx_l == -1:
                        local_minus_idx_l = idx
                    local_minus_idx_r = idx
                    
                local_nums.append(num)
            # 0がきたら一回計算
            else:
                zero_idx_r = idx
                if len(local_nums) != 0:
                    
                    if len(local_nums) == 1:
                        max_ = max(max_, local_sumproduct)
                    # 偶数のときは単純に全ての積
                    elif count_minus % 2 == 0:
                        max_ = max(max_, local_sumproduct)
                    # 奇数のときは、マイナスを外す
                    elif count_minus == 1:
                        a = prod(nums[zero_idx_l+1:local_minus_idx_l])
                        b = prod(nums[local_minus_idx_l+1:zero_idx_r])
                        n = []
                        if a is not None:
                            n.append(a)
                        if b is not None:
                            n.append(b)
                        max_ = max(n+[max_])
                    else:
                        a = prod(nums[local_minus_idx_l+1:zero_idx_r])
                        b = prod(nums[zero_idx_l+1:local_minus_idx_r])
                        max_ = max(a,b,max_)
                        n = []
                        if a is not None:
                            n.append(a)
                        if b is not None:
                            n.append(b)
                        max_ = max(n+[max_])
                        
                    max_ = max(0, max_)
                        
                # 初期化
                zero_idx_l = idx
                zero_idx_r = -1
                local_minus_idx_l = local_minus_idx_r = -1
                local_sumproduct = 1
                local_nums= []
                count_minus = 0
        
        # 最後の処理
        if len(local_nums) != 0:

            if len(local_nums) == 1:
                max_ = max(max_, local_sumproduct)

            # 偶数のときは単純に全ての積
            elif count_minus % 2 == 0:
                max_ = max(max_, local_sumproduct)
            # 奇数のときは、マイナスを外す
            elif count_minus == 1:
                a = prod(nums[zero_idx_l+1:local_minus_idx_l])
                b = prod(nums[local_minus_idx_r+1:])
                n = []
                if a is not None:
                    n.append(a)
                if b is not None:
                    n.append(b)
                max_ = max(n+[max_])
            else:
                a = prod(nums[local_minus_idx_l+1:])
                b = prod(nums[zero_idx_l+1:local_minus_idx_r])
                n = []
                if a is not None:
                    n.append(a)
                if b is not None:
                    n.append(b)
                max_ = max(n+[max_])
        
        
        return max_