Python程序：查找子数组模m后的最大和

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的末尾插入(csum的最后一个元素 + x) mod m
  • 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))

输入

"pptpp", [(1,1),(1,4),(1,1),(0,2)]

输出

3

更新于： 2021年10月11日

229 次查看

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告