Chương trình tìm tổng lớn nhất của tất cả các stack sau khi pop một số phần tử trong Python

Giả sử chúng ta có một danh sách các stack, chúng ta có thể lấy bất kỳ stack nào và pop bất kỳ số lượng phần tử nào từ nó. Chúng ta phải tìm tổng lớn nhất có thể đạt được sao cho tất cả các stack có cùng giá trị tổng.

Ví dụ, nếu đầu vào là stacks = [[3, 4, 5, 6], [5, 6, 1, 4, 4], [10, 2, 2, 2]], thì đầu ra sẽ là 12, vì chúng ta có thể thực hiện các thao tác như sau:

• Pop [6] từ stack đầu tiên, được [3, 4, 5], tổng là 12.
• Pop [4, 4] từ stack thứ hai, được [5, 6, 1], tổng là 12.
• Pop [2, 2] từ stack thứ ba, được [10, 2], tổng là 12.

Để giải quyết, chúng ta thực hiện các bước sau:

• sums := một map rỗng
• với mỗi stk trong stacks:
  • s := 0
  • với mỗi n trong stk:
    • s := s + n
    • sums[s] := sums[s] + 1
• ans := 0
• với mỗi cặp khóa-giá trị (s, f) của sums:
  • nếu f >= số lượng stack VÀ s > ans:
    • ans := s
• trả về ans

Ví dụ

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))

Input

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

Output

12