leetcode 152.積最大サブ配列(python)
leetcode 152.積最大サブ配列(python)
整数配列
例1:
例2:
メソッド-ダイナミックプランニング
整数配列
nums
を与えます.配列内の積が最も大きい連続サブ配列(少なくとも1つの数値を含む)を見つけ、サブ配列に対応する積を返します.例1:
: [2,3,-2,4]
: 6
: [2,3] 6。
例2:
: [-2,0,-1]
: 0
: 2, [-2,-1] 。
メソッド-ダイナミックプランニング
class Solution(object):
def maxProduct(self, nums):
mi = ma = res = nums[0]
for i in range(1, len(nums)):
if nums[i] < 0:
mi, ma = ma, mi
ma = max(ma * nums[i], nums[i])
mi = min(mi * nums[i], nums[i])
res = max(res, ma)
return res