Pythonで循環サブリストの最大合計を見つけるプログラム

numsの数のリストがあると仮定し、numsの開始と終了が隣接しているnumsの循環リストを考えてみましょう。循環リストで空でないサブリストの最大合計を見つける必要があります。

したがって、入力がnums =[2、3、-7、4、5]のような場合、合計が14になるサブリスト[4、5、2、3]を取得できるため、出力は14になります。

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

• max_sum：=負の無限大、cur_max：=0

• min_sum：=正の無限大、cur_min：=0

• numsのnumごとに、実行します

  • cur_max：=numの最大値とcur_max+ num

  • max_sum：=max_sumとcur_maxの最大値

  • cur_min：=numの最小値とcur_min+ num

  • min_sum：=min_sumとcur_minの最小値

• max_sum <=0の場合、

  • max_sumを返す

• max_sumと（numsのすべての要素の合計-min_sum）の最大値を返します

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

例

import math
class Solution:
   def solve(self, nums):
      max_sum = -math.inf
      cur_max = 0
      min_sum = math.inf
      cur_min = 0
      for num in nums:
         cur_max = max(num, cur_max + num)
         max_sum = max(max_sum, cur_max)
         cur_min = min(num, cur_min + num)
         min_sum = min(min_sum, cur_min)
      if max_sum <= 0:
         return max_sum
      return max(max_sum, sum(nums) - min_sum)
ob = Solution()
nums = [2, 3, -7, 4, 5]
print(ob.solve(nums))

入力

[2, 3, -7, 4, 5]

出力

14