[LeetCode] 0152. 最大積サブ配列

Python、C++、JavaScript、SQL、TypeScript の多様な LeetCode ソリューションを探索してください。面接の準備、学習、複数のプログラミング言語でのコードの練習に最適です。 Github リポジトリリンク

中くらい

整数配列が与えられた場合 数字、最大の積を持つサブ配列を見つけて、積を返します。

テストケースは、答えが範囲内に収まるように生成されます。 32ビット整数。

例 1:

入力： 数値 = [2,3,-2,4]
出力： 6
説明： [2,3] には最大の積 6 があります。

例 2:

入力： 数値 = [-2,0,-1]
出力： 0
説明： [-2,-1] は部分配列ではないため、結果が 2 になることはありません。

制約:

1 <= nums.length <= 2*10 ⁴
-10 <= nums[i] <= 10
次の部分配列の積 数字 は 保証された に収まる 32ビット 整数。

パイソン

				
					# 時間計算量: O(n) # 空間計算量: import リスト クラスの入力による O(1) 解決策: def maxProduct(self, nums: List[int]) -> int: if len(nums) == 0: return 0 maxSoFar, minSoFar, result = nums[0], nums[0], nums[0] for i in range(1, len(nums)): curr = nums[i] tempMax = max(curr, max(maxSoFar * curr) , minSoFar * curr)) minSoFar = min(curr, min(maxSoFar * curr, minSoFar * curr)) maxSoFar = tempMax result = max(result, maxSoFar) return result nums = [-2, 0, -1] print(Solution) ().maxProduct(nums))

中くらい

パイソン

関連記事