Pythonで適切なサブアレイの最大スコアを見つけるプログラム

numsという配列と値kがあるとします。サブアレイのスコア（i、j）がサブアレイnums [i..j] *（j-i + 1）の最小値として定義されていると考えてください。ここで、適切なサブアレイは、i <=k<=jであるサブアレイです。良いサブアレイの可能な最大スコアを見つける必要があります。

したがって、入力がnums =[2,5,4,8,5,6] k =3のような場合、最適なサブ配列はここ（1、5）にあるため、出力は20になり、nums[1の最小値になります。 ..5]は4なので、4 *（5-1 + 1）=20

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

• ans：=nums [k]、minNum：=nums [k]

• i：=k、j：=k

• i>-1またはj

  • i>-1およびnums[i]>=minNumの場合、実行

    • i：=i-1

  • j=minNum、do

    • j：=j + 1

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

  • minNum：=最大値（i> -1の場合はnums[i]、それ以外の場合は-1）および（jの場合はnums[j] <それ以外の場合はnumsのサイズ-1）

• ansを返す

例

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

def solve(nums, k):
   ans = nums[k]
   minNum = nums[k]
   i = k
   j = k
   while i > -1 or j < len(nums):
      while i > -1 and nums[i] >= minNum:
         i -= 1
      while j < len(nums) and nums[j] >= minNum:
         j += 1
      ans = max(ans, (j - i - 1) * minNum)
      minNum = max(nums[i] if i > -1 else -1 , nums[j] if j <
len(nums) else -1)
   return ans

nums = [2,5,4,8,5,6]
k = 3
print(solve(nums, k))

入力

[2,5,4,8,5,6], 3

出力

20