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

numsと呼ばれる数値のリストがあるとすると、隣接していない数値の最大の合計を返す関数を定義します。ここでは、数値は0または負の数にすることができます。

したがって、入力が[3、5、7、3、6]の場合、出力は16になります。これは、get16に3、7、および6を取ることができるためです。

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

• numsのサイズが<=2の場合、

  • 最大数を返す

• noTake：=0

• 取る：=nums [0]

• 1からnumsのサイズの範囲のiの場合、実行します

  • take：=noTake + nums [i]

  • noTake：=最大のnoTakeとtake

• noTakeとtakeの最大値を返します

理解を深めるために、次の実装を見てみましょう-

例

class Solution:
   def solve(self, nums):
      if len(nums) <= 2:
         return max(nums)
      noTake = 0
      take = nums[0]
      for i in range(1, len(nums)):
         take, noTake = noTake + nums[i], max(noTake, take)
         return max(noTake, take)
ob = Solution()
nums = [3, 5, 7, 3, 6]
print(ob.solve(nums))

入力

[3, 5, 7, 3, 6]

出力

16