在Python中以m为模求子数组的最大和的程序

  • Z时代
  • 2024-01-10
  • 分类：综合

在Python中以m为模求子数组的最大和的程序

假设我们有一个包含 n 个元素的数组 nums。我们还有另一个整数 m。我们必须找到以 m 为模的任何子数组的和的最大值。

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

  • [1] 模 5 = 1

  • [5] 模 5 = 0

  • [7] 模 5 = 2

  • [3] 模 5 = 3

  • [1,5] 模 5 = 1

  • [5,7] 模 5 = 2

  • [7,3] 模 5 = 0

  • [1,5,7] 模 5 = 3

  • [5,7,3] 模 5 = 0

  • [1,5,7,3] 模 5 = 1

示例

让我们看看以下实现以获得更好的理解 -

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

输入

"pptpp", [(1,1),(1,4),(1,1),(0,2)]
输出结果
3

以上是 在Python中以m为模求子数组的最大和的程序 的全部内容， 来源链接： utcz.com/z/355706.html

回到顶部