Pythonで最小AとAのサイズの積が最大になるサブリストのサイズを見つけるプログラム

numsと呼ばれる数値のリストと別の値posがあるとします。 （Aの最小値）*（Aのサイズ）が最大化されるようなインデックスposを含むnumsのサブリストAを見つけて、値を返す必要があります。

したがって、入力がnums =[-2、2、5、4] pos =3の場合、（5、4）=4であり、（5、4）=4であるため、最適なサブリストは[5、4]であるため、出力は8になります。サイズは2で、4 * 2=8です。

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

• ans：=A [pos]、m：=A [pos]

• i：=pos、j：=pos

• 0からA-1のサイズの範囲のiに対して、次の手順を実行します。

  • left：=A [i --1] if i --1>=0それ以外の場合-inf

  • right：=A [j + 1] if j +1

  • 左>=右の場合、

    • i：=i-1

    • m：=mとA[i]

      の最小値

  • それ以外の場合

    • j：=j + 1

    • m：=mとA[j]

      の最小値

  • ans：=ansの最大値と（m *（j --i + 1））

• ansを返す

例

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

class Solution:
   def solve(self, A, pos):
      NINF = float("-inf")
      ans = m = A[pos]
      i = pos
      j = pos
      for _ in range(len(A) - 1):
         left = A[i - 1] if i - 1 >= 0 else NINF
         right = A[j + 1] if j + 1 < len(A) else NINF
         if left >= right:
            i -= 1
            m = min(m, A[i])
         else:
            j += 1
            m = min(m, A[j])
         ans = max(ans, m * (j - i + 1))
      return ans
ob = Solution()
nums = [-2, 2, 5, 4]
pos = 3
print(ob.solve(nums, pos))

入力

[-2, 2, 5, 4], 3

出力

8