Chương trình tìm tổng tối đa của modulo mảng con theo m trong Python

Giả sử chúng ta có một nums mảng với n phần tử. Ta có một số nguyên khác m. Chúng ta phải tìm tổng giá trị lớn nhất của bất kỳ môđun con nào của nó.

Vì vậy, nếu đầu vào là nums =[1,5,7,3] m =5, thì đầu ra sẽ là 3 vì

[1] mod 5 =1
[5] mod 5 =0
[7] mod 5 =2
[3] mod 5 =3
[1,5] mod 5 =1
[5,7] mod 5 =2
[7,3] mod 5 =0
[1,5,7] mod 5 =3
[5,7,3] mod 5 =0
[1,5,7,3] mod 5 =1

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

csum:=một danh sách và ban đầu chèn nums [0] mod m vào đó
đối với mỗi x trong nums ngoại trừ giá trị đầu tiên, hãy thực hiện
- chèn (mục cuối cùng của csum + x) mod m vào cuối csum
saw:=một danh sách có một phần tử ban đầu là 0
max_sum:=-1
đối với mỗi s trong csum, thực hiện
- idx:=vị trí ngoài cùng bên trái để chèn s vào thấy để danh sách được sắp xếp
- if idx
- max_sum:=tối đa là max_sum và s
nếu không,
- chèn s ở phía ngoài cùng bên trái của chỉ mục đã thấy để mảng được sắp xếp
chèn s ở phía ngoài cùng bên trái của chỉ mục đã thấy để mảng được sắp xếp

trả về max_sum

Ví dụ

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

import bisect
def solve(nums, m):
   csum = [nums[0] % m]
   for x in nums[1:]:
      csum.append((csum[-1] + x) % m)

   seen = [0]
   max_sum = -1
   for s in csum:
      idx = bisect.bisect_left(seen, s)
      if idx < len(seen):
         max_sum = max(max_sum, s, (s - seen[idx]) % m)
      else:
         max_sum = max(max_sum, s)
      bisect.insort_left(seen, s)

   return max_sum

nums = [1,5,7,3]
m = 5
print(solve(nums, m))

Đầu vào

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

Chương trình tìm tổng tối đa của modulo mảng con theo m trong Python

Ví dụ

Đầu vào

Đầu ra