Pythonで循環リスト内の隣接しない要素の最大合計を求めるプログラム

問題の概要

数値のリスト nums が与えられ、これが循環リスト（最初の要素と最後の要素がつながっているリスト）を表しているとします。この中から互いに隣接していない要素を選び、その合計の最大値を求めるのが目的です。

例えば、入力が nums = [10, 3, 4, 8] の場合、出力は 14 になります。これは 10 と 4 を選べるためです。一方、10 と 8 は循環リスト上で隣接しているため、同時に選ぶことはできません。

解法のアプローチ

循環リストでは最初と最後の要素が隣接関係にあるため、そのまま通常の「隣接しない要素の最大和」問題として扱うことはできません。そこで、問題を次のように2つに分割します。

• n := nums のサイズ
• nums1 := nums[0] から nums[n-2] まで（最後の要素を除外したリスト）
• nums2 := nums[1] から末尾まで（最初の要素を除外したリスト）

この分割により、どちらのリストも最初と最後が隣接しない通常のリストになるため、標準的な手法で解けるようになります。

関数 f() の定義（nums1 用）

• 引数 i を受け取る再帰関数です
• i >= len(nums1) の場合は 0 を返します
• それ以外の場合は max(nums1[i] + f(i + 2), f(i + 1)) を返します

関数 g() の定義（nums2 用）

• 引数 j を受け取る再帰関数です
• j >= len(nums2) の場合は 0 を返します
• それ以外の場合は max(nums2[j] + g(j + 2), g(j + 1)) を返します

メイン処理では、両方の結果を比較して max(f(0), g(0)) を返します。これにより、「最初の要素を含む場合」と「含まない場合」のどちらか大きい方が答えになります。

実装例

class Solution:
    def solve(self, nums):
        n = len(nums)
        nums1 = nums[: n - 1]
        nums2 = nums[1:]
        def f(i):
            if i >= len(nums1):
                return 0
            return max(nums1[i] + f(i + 2), f(i + 1))
        def g(j):
            if j >= len(nums2):
                return 0
            return max(nums2[j] + g(j + 2), g(j + 1))
        return max(f(0), g(0))
ob = Solution()
nums = [10, 3, 4, 8]
print(ob.solve(nums))

入力

[10, 3, 4, 8]

出力

14

補足：計算量について

上記の素朴な再帰実装は、各要素で「選ぶ／選ばない」の2択を繰り返すため、時間計算量は O(2^n) となります。リストが長くなると非効率になるため、実務ではメモ化（lru_cache など）や動的計画法（DP）を組み合わせて O(n) に改善するのが一般的です。考え方の基本である「循環リストを2つの線形リストに分割する」点は変わりません。