Pythonの循環リストで隣接していない要素の合計を見つけるプログラム

循環リストを表すnumsという番号のリストがあるとします。隣接していない数の最大の合計を見つける必要があります。

したがって、入力がnums =[10、3、4、8]の場合、出力は14になります。これは、10と4を取ることができるためです。10と8は隣接しているため、取ることができません。

これを解決するには、次の手順に従います-

• n：=numsのサイズ
• nums1：=nums[インデックス0からn-2まで]
• nums2：=nums[インデックス1から終了まで]
• 関数f（）を定義します。これには時間がかかります
• i> =nums1のサイズの場合、
  • 0を返す
• 最大数のnums1[i]+ f（i + 2）およびf（i + 1）を返します
• 関数g（）を定義します。これにはjがかかります
• j> =nums2のサイズの場合、
  • 0を返す
• 最大数のnums2[j]+ g（j + 2）およびg（j + 1）を返します
• メインの方法から次のようにします-
• 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