- ブルートフォース法: 最も単純な解法は、配列を順番にスキャンし、連続した1の数をカウントする方法です。この方法では、配列内のすべての要素をチェックするため、時間計算量はO(n)となります。
def find_max_consecutive_ones(nums):
max_count = 0
count = 0
for num in nums:
if num == 1:
count += 1
max_count = max(max_count, count)
else:
count = 0
return max_count- スライディングウィンドウ: 配列を一度だけスキャンする方法として、スライディングウィンドウを使用することができます。ウィンドウ内の連続した1の数を追跡し、最長の連続1の数を更新します。この方法も時間計算量はO(n)です。
def find_max_consecutive_ones(nums):
max_count = 0
count = 0
left = 0
for right in range(len(nums)):
if nums[right] == 0:
count = 0
left = right + 1
else:
count += 1
max_count = max(max_count, count)
return max_count- 動的計画法: 動的計画法を使用して、配列の各要素について最長の連続1の数を計算する方法もあります。これにより、配列を一度だけスキャンして結果を得ることができます。時間計算量はO(n)です。
def find_max_consecutive_ones(nums):
dp = [0] * len(nums)
dp[0] = nums[0]
max_count = dp[0]
for i in range(1, len(nums)):
if nums[i] == 1:
dp[i] = dp[i-1] + 1
max_count = max(max_count, dp[i])
return max_countこれらの方法は、最大連続1のアルゴリズムの効率的な解法です。ブルートフォース法はシンプルで実装が容易ですが、スライディングウィンドウや動的計画法の方がより効率的です。パフォーマンスを最適化するためには、問題の制約条件や要件に応じて最適なアルゴリズムを選択することが重要です。
また、LeetCodeの問題には他の解法も存在する可能性があります。この記事ではいくつかの一般的な解法を紹介しましたが、さまざまな方法やアルゴリズムを試してみることをおすすめします。