在Python中查找子数组模M的最大和的程序

假设我们有一个由n个元素组成的数组nums。我们有另一个整数m。我们必须找到其任何子数组和模m的最大值。

因此，如果输入是nums = [1,5,7,3]，m = 5，那么输出将为3，因为

[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

为了解决这个问题，我们将遵循以下步骤−

csum：一个列表，最初将nums [0] mod m插入其中
对于nums中除第一个值以外的每个x，执行以下操作：
- 将(csum的最后一项+x) mod m插入csum的末尾
seen：一个具有单个元素的列表，最初为0
max_sum：-1
对于csum中的每个s，执行以下操作：
- idx：最左侧的位置插入s到seen中，以使列表排序
- 如果idx < seen的大小，则
  - max_sum：最大值为max_sum和s
- 否则，
  - 将s插入seen的最左侧索引，以使数组排序
- 将s插入seen的最左侧索引，以使数组排序
返回max_sum

示例

让我们看一下以下实现以更好地理解−

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