Pythonで同じ合計の3つの重複しないサブリストの最大合計を見つけるプログラム

numsと呼ばれる数値のリストと別の値kがあるとすると、サイズkの指定されたリストの3つの重複しないサブリストの最大の合計を見つける必要があります。

したがって、入力がnums =[2、2、2、-6、4、4、4、-8、3、3、3] k =3のような場合、出力は27になり、サブリスト[2、2、2]、[4、4、4]、および[3、3、3]、合計は27です。

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

• P：=[0]
• Aのxごとに、
  • Pの最後にP[-1]+xを挿入します
• Q：=[P [i + K] --P [i] for i in range 0 to size of P --K]
• プレフィックス：=Q[インデックス0から終了まで]
• サフィックス：=Q[インデックス0から終了まで]
• 範囲0からQ-1のサイズのiの場合、実行
  • prefix [i + 1]：=プレフィックスの最大値[i + 1]、プレフィックス[i]
  • 接尾辞[〜（i + 1）]：=接尾辞の最大値[〜（i + 1）]、接尾辞[〜i]
• ret =（Q[i]+プレフィックス[i-K]+サフィックス[i+K]）KからQ-K-1のサイズまでの各iに対して
• retの最大値を返す

例（Python）

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

class Solution:
   def solve(self, A, K):
      P = [0]
      for x in A:
         P.append(P[-1] + x)
      Q = [P[i + K] - P[i] for i in range(len(P) - K)]
      prefix = Q[:]
      suffix = Q[:]
      for i in range(len(Q) - 1):
         prefix[i + 1] = max(prefix[i + 1], prefix[i])
         suffix[~(i + 1)] = max(suffix[~(i + 1)], suffix[~i])
      return max(Q[i] + prefix[i - K] + suffix[i + K] for i in range(K, len(Q) - K))
ob = Solution()
nums = [2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3]
k = 3
print(ob.solve(nums, k))

入力

[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3], 3

出力

27