Pythonで数値リストのすべてのサブシーケンスの幅の合計を見つけるプログラム

numsと呼ばれる数のリストがあるとします。数列の最大数と最小数の差としての数列の幅。 numsのすべてのサブシーケンスの幅の合計を見つける必要があります。答えが非常に大きい場合は、結果を10 ^ 9+7で変更します。

したがって、入力がnums =[7、4、9]の場合、出力は15になります。これは、[7]、[4]、[9]、[7、4]、[のようなサブシーケンスがあるためです。 7、9]、[4、9]、[7、4、9]であるため、幅は0、0、0、3、2、5、5なので、15を取得します。

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

• m：=10 ^ 9 + 7

• リスト番号を並べ替える

• ans：=0

• power：=（nums + 1）と同じサイズのリストで、1で埋めます

• 範囲1からnums+1のサイズのiの場合、実行します

  • power [i]：=power [i-1] * 2 mod m

  • 0からnumsのサイズの範囲のiの場合、実行します

    • 正：=（power [i]-1）* nums [i]

    • 負の数：=（power [size of nums --i --1]-1）* nums [i]

    • ans：=（ans +正-負）mod m

• ansを返す

例

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

class Solution:
   def solve(self, nums):
      m = 10**9 + 7
      nums.sort()
      ans = 0
      power = [1] * (len(nums) + 1)
      for i in range(1, len(nums) + 1):
         power[i] = power[i - 1] * 2 % m
      for i in range(0, len(nums)):
         positive = (power[i] - 1) * nums[i]
         negative = (power[len(nums) - i - 1] - 1) * nums[i]
         ans = (ans + positive - negative) % m
      return ans
ob = Solution()
nums = [7, 4, 9]
print(ob.solve(nums))

入力

[7, 4, 9]

出力

15