Pythonを使用してソートされたサブ配列の合計の範囲の合計を見つけるプログラム

n個の正の要素を持つ配列numがあるとします。 numsの空でない連続するすべてのサブ配列の合計を計算し、n *（n + 1）/ 2の数値の新しい配列を作成することにより、それらを減少しない方法で並べ替えるとします。新しい配列で、インデックス左からインデックス右（1インデックス）までの数値の合計を見つける必要があります。答えは非常に大きい可能性があるため、10 ^ 9+7を法とする結果を返します。

したがって、入力がnums =[1,5,2,6] left =1 right =5のような場合、ここではすべてのサブ配列の合計が1、5、2、6、6、7、8であるため、出力は20になります。 、8、13、14なので、並べ替え後は[1,2,5,6,6,7,8,8,13,14]になり、インデックス1から5までの要素の合計は1 + 5+2になります。 + 6 + 6=20。

これを解決するには、次の手順に従います-

• m：=10 ^ 9 + 7

• n：=numsのサイズ

• a：=新しいリスト

• 0からn-1の範囲のiの場合、実行

  • iからn-1の範囲のjの場合、実行

    • iがjと同じ場合、

      • 
        

      の最後にnums[j]を挿入します

    • それ以外の場合

      • の最後に（（nums [j] + aの最後の要素）mod m）を挿入します

• リストを並べ替える

• sm：=a [インデックス左から1から右へ]）のすべての要素の合計

• smmodmを返す

理解を深めるために、次の実装を見てみましょう-

例

def solve(nums, left, right):
   m = 10**9 + 7
   n = len(nums)
   a=[]
   for i in range(n):
      for j in range(i,n):
         if i==j:
            a.append(nums[j])
         else:
            a.append((nums[j]+a[-1])%m)
   a.sort()
   sm=sum(a[left-1:right])
   return sm % m
nums = [1,5,2,6]
left = 1
right = 5
print(solve(nums, left, right))

入力

[1,5,2,6], 1, 5

出力

20