Pythonでmを法とする部分配列の最大合計を見つけるプログラム

Pythonでmを法とする部分配列の最大合計を見つけるプログラム

n個の要素を持つ配列numがあるとします。別の整数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]modmをリストに挿入します
• 最初の値を除くnumsの各xについて、実行します
  • csumの最後に（csum + xの最後の項目）modmを挿入します
• sawed：=最初は0である単一の要素を持つリスト
• max_sum：=-1
• csumの各sについて、
  • idx：=リストがソートされるようにsを挿入する左端の位置
  • idx <見たサイズの場合、
    • max_sum：=max_sumとsの最大値
  • それ以外の場合、
    • 配列がソートされるように、表示の左端のインデックスにsを挿入します
  • 配列がソートされるように、表示の左端のインデックスにsを挿入します
• 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