Pythonでいくつかの要素をポップした後、すべてのスタックの最大合計をチェックするプログラム

スタックのリストがあるとすると、任意のスタックを取得して、そこから任意の数の要素をポップできます。すべてのスタックが同じ合計値を持つように、達成できる最大の合計を見つける必要があります。

したがって、入力がstacks =[[3、4、5、6]、[5、6、1、4、4]、[10、2、2、2]]のような場合、出力は12になります。 -

• 最初のスタックから[6]をポップすると、[3、4、5]の合計は12になります。

• 2番目のスタックから[4,4]をポップすると、[5、6、1]の合計は12になります。

• 3番目のスタックから[2,2]をポップすると、[10、2]の合計は12になります。

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

• 合計：=空のマップ

• スタック内の各stkについて、実行します

  • s：=0

  • stkのnごとに、実行します

    • s：=s + n

    • sums [s]：=sums [s] + 1

• ans：=0

• 合計のキー値ペア（s、f）ごとに、実行します

  • f>=スタックカウントおよびs>ansの場合、

    • ans：=s

• ansを返す

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

例

from collections import defaultdict
class Solution:
   def solve(self, stacks):
      sums = defaultdict(int)
      for stk in stacks:
         s = 0
         for n in stk:
            s += n
            sums[s] += 1
         ans = 0
         for s, f in sums.items():
            if f >= len(stacks) and s > ans:
               ans = s
         return ans
ob1 = Solution()
stacks = [
   [3, 4, 5, 6],
   [5, 6, 1, 4, 4],
   [10, 2, 2, 2]
]
print(ob1.solve(stacks))

入力

stacks = [ [3, 4, 5, 6], [5, 6, 1, 4, 4], [10, 2, 2, 2] ]

出力

12