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

numsと呼ばれる数値のリストと、k回連結されたnumsの大きなリストを表す別の値kがあるとします。合計が最大の連続するサブリストの合計を見つける必要があります。

したがって、入力がnums =[1、3、4、-5]、k =1の場合、[2、4、5]

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

• s：=ans：=lo：=0
• 0からkおよび2の最小値までの範囲のすべての値について、実行します
  • numsのxごとに、
    • s：=s + x
    • lo：=最小のlo、s
    • ans：=ansの最大値、s --lo
• ans +最大値0およびnumsのすべての要素の合計*最大値0および（k-2）を返します

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

例

class Solution:
   def solve(self, nums, k):
      s = ans = lo = 0
      for _ in range(min(k, 2)):
         for x in nums:
            s += x
            lo = min(lo, s)
         ans = max(ans, s - lo)
      return ans + max(0, sum(nums)) * max(0, (k - 2))
ob = Solution()
nums = [2, 4, 5, -4]
k = 1
print(ob.solve(nums, k))

入力

[2, 4, 5, -4], 1

出力

11