Pythonで一定速度で走行した最長区間（サブリスト）の長さを求めるアルゴリズム

等間隔の時間ごとに記録された車の位置を表す数値のリストが与えられたとき、車が一定の速度で走行していた最も長い連続区間（サブリスト）のサイズを求める問題を考えてみましょう。

例えば、入力が positions = [0, 4, 8, 12, 6, 4, 0] の場合、出力は 4 になります。これは部分リスト [0, 4, 8, 12] の間、各ステップでの移動距離が常に「4」で一定だからです。

解法のアプローチ

この問題は、隣接する2点間の移動距離を順番に比較していくことで解決できます。具体的な手順は以下の通りです。

• 変数 j = 1 で走査を開始します。
• 最大カウント max_cnt = 0、現在のカウント current = 0 を初期化します。
• 最初の2点間の距離 distance = |positions[0] - positions[1]| を基準として設定します。
• j がリストの末尾に達するまで、以下を繰り返します。
  • 直前の位置 prev = positions[j - 1] を取得します。
  • distance が |positions[j] - prev| と等しければ、速度が一定なので current を +1 します。
  • 等しくなければ、max_cnt を更新し、current を 1 にリセットして、新しい distance を設定します。
  • 毎回 max_cnt = max(max_cnt, current) で最大値を更新します。
• 最後に max_cnt + 1 を返します（区間の要素数は「移動回数 + 1」となるため）。

実装例

それでは、実際のPythonコードを見てみましょう。

class Solution:
    def solve(self, positions):
        j = 1
        max_cnt = 0
        current = 0
        distance = abs(positions[0] - positions[1])
        while j < len(positions):
            prev = positions[j - 1]
            if distance == abs(positions[j] - prev):
                current += 1
            else:
                max_cnt = max(max_cnt, current)
                current = 1
                distance = abs(positions[j] - prev)
            max_cnt = max(max_cnt, current)
            j += 1
        return max_cnt + 1

ob = Solution()
positions = [0, 4, 8, 12, 6, 4, 0]
print(ob.solve(positions))

入力

[0, 4, 8, 12, 6, 4, 0]

出力

4

計算量について

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は定数であるため空間計算量は O(1) となります。位置データの件数が多くても効率的に処理できるのが特徴です。