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 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始學習
廣告