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

在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