Pythonで数値リストのすべての部分列の幅の合計を効率的に求めるプログラム

数値のリスト nums が与えられたとします。ここで、ある数列の「幅」とは、その数列に含まれる最大値と最小値の差として定義します。このとき、nums のすべての部分列（サブシーケンス）の幅を求め、それらの合計を計算します。結果が非常に大きな数になる場合は、10⁹+7 で割った余りを返してください。

例えば、入力が nums = [7, 4, 9] の場合、出力は 15 になります。考えられる部分列は [7]、[4]、[9]、[7, 4]、[7, 9]、[4, 9]、[7, 4, 9] の7つで、それぞれの幅は 0、0、0、3、2、5、5 となるため、その合計は 15 になるからです。

解法のアプローチ

すべての部分列を実際に生成して幅を計算するのは非効率です（部分列の数は 2ⁿ 個に爆発します）。そこで、次の手順で数学的に効率よく求めます。

• m := 10⁹ + 7

• リスト nums をソートする

• ans := 0

• power := 長さが (len(nums) + 1) のリストを作成し、すべて 1 で初期化する

• i を 1 から len(nums) まで繰り返す：

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

• i を 0 から len(nums) - 1 まで繰り返す：

  • positive := (power[i] - 1) * nums[i]

  • negative := (power[len(nums) - i - 1] - 1) * nums[i]

  • ans := (ans + positive - negative) mod m

• ans を返す

なぜこの方法で求まるのか？

リストをソートすると、インデックス i の要素 nums[i] より小さい要素がちょうど i 個存在します。部分集合の選び方を考えると、nums[i] が部分列の最大値になるのは 2ⁱ 回、最小値になるのは 2^(n-1-i) 回です。要素が単独で部分列になる場合は幅が 0 となるため、それぞれ 1 を引いた値を掛けて寄与を計算します。全要素について「最大値としての寄与」から「最小値としての寄与」を差し引いて合計すれば、すべての部分列の幅の総和が求まります。

Python実装例

以下の実装を見ると、理解がより深まるでしょう。

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

計算量

このアルゴリズムの時間計算量は O(n log n)（ソート処理が支配的）、空間計算量は O(n) です。全部分列を列挙する O(2ⁿ) の素朴なアプローチと比べ、大幅に高速に動作します。