Chương trình tìm tổng lớn nhất của 3 danh sách con không chồng chéo của cùng một tổng trong Python

Giả sử chúng ta có một danh sách các số được gọi là num và một giá trị khác k, chúng ta phải tìm tổng lớn nhất của ba danh sách con không trùng nhau của danh sách đã cho có kích thước k.

Vì vậy, nếu đầu vào là nums =[2, 2, 2, -6, 4, 4, 4, -8, 3, 3, 3] k =3, thì đầu ra sẽ là 27, vì chúng ta có thể chọn danh sách con [2, 2, 2], [4, 4, 4] và [3, 3, 3], tổng số tiền là 27.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• P:=[0]
• với mỗi x trong A, thực hiện
  • chèn P [-1] + x vào cuối P
• Q:=[P [i + K] - P [i] cho tôi trong phạm vi từ 0 đến kích thước là P - K]
• tiền tố:=Q [từ chỉ mục 0 đến cuối]
• hậu tố:=Q [từ chỉ mục 0 đến cuối]
• đối với tôi trong phạm vi từ 0 đến kích thước Q - 1, thực hiện
  • tiền tố [i + 1]:=tối đa tiền tố [i + 1], tiền tố [i]
  • hậu tố [~ (i + 1)]:=tối đa là hậu tố [~ (i + 1)], hậu tố [~ i]
• ret =(Q [i] + tiền tố [i - K] + hậu tố [i + K]) cho mỗi i trong phạm vi K đến kích thước của Q - K - 1
• trả về tối đa là ret

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

27