Pythonで最大サブアレイ最小積を見つけるプログラム

配列numsがあるとすると、numsの空でない各サブ配列の最大最小積を見つける必要があります。答えは十分に大きい可能性があるため、10 ^ 9+7を法として返します。配列の最小積は、配列の最小値に配列の合計を掛けたものに等しくなります。したがって、[4,3,6]（最小値は3）のような配列がある場合、最小積は3 *（4 + 3 + 6）=3 * 13=39になります。

したがって、入力がnums =[2,3,4,3]のような場合、結果を最大化するためのサブ配列[3,4,3]を取得できるため、出力は30になります。したがって、3 *（3 + 4 + 3）=3 * 10=30。

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

• m：=10 ^ 9 + 7

• スタック：=新しいスタック

• rsum：=0、res：=0

• numsの最後に0を挿入します

• インデックスiと値v（nums）ごとに、実行します

  • スタックが空ではなく、nums[スタックの最上位のインデックス]>=vの場合、実行

    • index、val）：=スタックの一番上にあり、スタックからポップします

    • arrSum：=rsum

    • スタックが空でない場合は、

      • arrSum：=rsum-スタックの最上位の値

    • res：=resと（nums [index] * arrSum）の最大値

  • rsum：=rsum + v

  • スタックの最後で（i、rsum）をプッシュします

• resmodmを返す

例

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

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