Pythonのスタックのリストからポップされたk要素の最大合計を見つけるプログラム

スタックのリストと整数kがあるとします。スタックの任意の組み合わせから正確にk個の要素をポップオフすることで達成できる最大の合計を見つける必要があります。

したがって、入力がスタック=[[50、-4、-15]、[2]、[6、7、8]]、k =4のような場合、すべてをポップオフできるため、出力は39になります。最初のスタックから3つの要素を取り出し、最後のスタックの最後の要素をポップして、-15 + -4 + 50 + 8=39を取得します。

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

• 関数rec（）を定義します。これにはi、nが必要です

• nがkと同じ場合、

  • 0を返す

• n> kの場合、

  • 負の無限大を返す

• iがスタックの数と同じである場合、

  • 負の無限大を返す

• iがスタックの数-1と同じである場合、

  • 必要：=k-n

  • 必要に応じて>スタックの要素数[i]、次に

    • 負の無限大を返す

  • それ以外の場合

    • stack[i]最後に必要な要素数の要素の合計を返す

• res：=-math.inf、su：=0

• スタックの範囲サイズのstiの場合[i]-1から0、

  1ずつ減らします。

  • su：=su + stacks [i、sti]

  • localres：=su + rec（i + 1、n+スタックのサイズ[i]--sti）

  • res：=resとlocalresの最大値

• resとrec（i + 1、n）の最大値を返す

• メインメソッドからrec（0、0）

  を呼び出します

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

例

import math

class Solution:
   def solve(self, stacks, k):
      def rec(i, n):
         if n == k:
            return 0
         if n > k:
            return -math.inf
         if i == len(stacks):
            return -math.inf
         if i == len(stacks) - 1:
            needed = k - n
            if needed > len(stacks[i]):
               return -math.inf
            else:
               return sum(stacks[i][-needed:])
         res, su = -math.inf, 0
         for sti in range(len(stacks[i]) - 1, -1, -1):
            su += stacks[i][sti]
            localres = su + rec(i + 1, n + len(stacks[i]) - sti)
            res = max(res, localres)
         return max(res, rec(i + 1, n))

      return rec(0, 0)

ob = Solution()
stacks = [
   [50, -4, -15],
   [2],
   [6, 7, 8]
]
k = 4
print(ob.solve(stacks, k))

入力

[[50, -4, -15],[2],[6, 7, 8]], 4

出力

39