用 Python 编写程序，求子数组以 m 为模的最大和

pythonserver side programmingprogramming更新于 2025/12/17 12:28:17

假设我们有一个包含 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 末尾插入 (csum 的最后一项 + x) mod m
seen := 一个最初只有一个元素的列表，该元素为 0
max_sum := -1
对于 csum 中的每个 s，执行
- idx := 将 s 插入到 seen 的最左边的位置，以便对列表进行排序
- 如果 idx <已看到的大小，则
  - max_sum := max_sum 和 s 的最大值
- 否则，
  - 将 s 插入到已看到最左边的索引处，以便数组已排序
- 将 s 插入到已看到最左边的索引处，以便数组已排序
返回 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))