在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
热门推荐
10 新年门口花束祝福语简短
11 盘锦结婚祝福语大全简短
12 父母生日祝福语 简短独特
13 家庭恩爱祝福语简短英文
14 高考俄语祝福语大全简短
15 虎年祝福语 诗句唯美简短
16 生日婚礼祝福语简短精辟
17 虎年喝酒拜年祝福语简短
18 教师闺蜜祝福语简短