Pythonのリストから各サブリストの最小値の合計を見つけるプログラム

numsという番号のリストがあるとします。すべてのサブリストxの最小xの合計をnumsで見つける必要があります。答えが大きすぎる場合は、結果を10 ^ 9+7で変更します。

したがって、入力がnums =[5、10、20、10、0]の場合、サブリストは[[5]、[10]、[20]、[10]、[ 0]、[5,10]、[10,20]、[20,10]、[10,0]、[5,10,20]、[10,20,10]、[20,10,0] 、[5,10,20,10]、[10,20,10,0]、[5,10,20,10,0]]であり、それらの最小値は[5、10、20、10、0、 5、10、10、0、5、10、0、5、0、0]なので、合計は90になります。

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

• ans：=0
• s：=新しいリスト
• temp_sum：=0
• nums単位のインデックスと値ごとに、
  • sと値<=sの最後のリストのインデックス1の要素である間、do
    • temp_sum：=temp_sum-sの最後のリストのインデックス2にある要素
    • sから最後の要素を削除する
  • sが空の場合、
    • sに3つの要素[index、value、（index + 1）*value]を含むリストを挿入します
  • それ以外の場合、
    • 3つの要素を持つリストを挿入します[index、value、（index-sの最後のリストの最初の要素）* value]
  • temp_sum：=temp_sum+sの最後のリストのインデックス2にある要素
  • ans：=ans + temp_sum
• return ans mod（10 ^ 9 + 7）

例

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

def solve(nums):
   ans = 0
   s = []
   temp_sum = 0
   for index, value in enumerate(nums):
      while s and value <= s[-1][1]:
         temp_sum -= s[-1][2]
         s.pop()
      if not s:
         s.append([index, value, (index + 1) * value])
      else:
         s.append([index, value, (index - s[-1][0]) * value])
      temp_sum += s[-1][2]
      ans += temp_sum
   return ans % (10**9 + 7)

nums = [5, 10, 20, 10, 0]
print(solve(nums))

入力

[5, 10, 20, 10, 0]

出力

90