Pythonで部分配列の最大最小積（min-product）を求めるプログラム

問題概要

配列 nums が与えられたとき、nums の各空でない部分配列について「最小積（min-product）」を計算し、その中で最大となる値を求めます。答えは非常に大きな数になる可能性があるため、10^9+7 を法とした剰余で返します。

ここで、配列の最小積とは「配列内の最小値 × 配列の要素の合計値」として定義されます。例えば、配列が [4,3,6] の場合、最小値は 3 なので、最小積は 3×(4+3+6) = 3×13 = 39 となります。

入力が nums = [2,3,4,3] の場合、出力は 30 になります。これは、部分配列 [3,4,3] を選ぶことで結果が最大化され、3×(3+4+3) = 3×10 = 30 となるためです。

解決のためのアプローチ

この問題は、単調スタック（monotonic stack）を活用することで効率的に解くことができます。具体的には、以下の手順に従います。

• m := 10^9+7（剰余を取るための定数）
• stack := 新しいスタック
• rsum := 0（累積和）、res := 0（結果）
• nums の末尾に 0 を挿入する（番兵として残りの要素をすべて処理させる）
• nums の各インデックス i と値 v に対して、以下を実行する
  • スタックが空でなく、スタックの先頭のインデックスに対応する nums の値が v 以上である間、次を繰り返す
    • スタックの先頭から (index, val) を取り出す（pop）
    • arrSum := rsum
    • スタックが空でなければ、arrSum := rsum − スタック先頭の累積和
    • res := res と (nums[index] × arrSum) の大きい方
  • rsum := rsum + v
  • (i, rsum) をスタックにプッシュする
• res mod m を返す

この手法では、各要素を「最小値」とする部分配列の範囲をスタックで管理しながら、累積和との積を順次評価していきます。これにより、全部分配列を素朴に列挙する O(n²) よりも効率的な計算が可能になります。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def solve(nums):
   m = int(1e9+7)
   stack = []
   rsum = 0
   res = 0

   nums.append(0)

   for i, v in enumerate(nums):
      while stack and nums[stack[-1][0]] >= v:
         index, _ = stack.pop()

         arrSum=rsum

         if stack:
            arrSum=rsum-stack[-1][1]

         res=max(res, nums[index]*arrSum)

      rsum += v
      stack.append((i, rsum))

   return res % m

nums = [2,3,4,3]
print(solve(nums))

入力

[2,3,4,3]

出力

30

このように、単調スタックと累積和を組み合わせることで、配列内のすべての部分配列の中から最小積の最大値を効率よく求めることができます。