Pythonで最大幅ランプを見つけるプログラム

配列numsがあるとすると、ランプはタプル（i、j）であり、i

したがって、入力がnums =[6,0,8,2,1,5]のようである場合、最大幅ランプは（i、j）=（1、5）およびnumsで達成されるため、出力は4になります。 [1]=0およびnums[5]=5。

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

• B：=新しい地図

• 0からnumsのサイズの範囲のiの場合、実行します

  • x：=nums [i]

  • xがBにある場合、

    • B [x]

      の最後にiを挿入します

  • それ以外の場合

    • B [x]：=[i]

• mini：=リストは最初に1つのinfをリストに格納します

• maxi：=リストは最初に1つの-infをリストに格納します

• Bのすべてのキーのリストリストを並べ替えるxごとに、実行します

  • miniの最後の要素の最小値とminiの最後にB[x]の最小値を挿入します

• Bのすべてのキーの逆にソートされたリストの各xについて、実行します

  • miniの最後の要素の最小値とminiの最後にB[x]の最小値を挿入します

• maxi：=reverse maxi次に、サブ配列を最初から最後から2番目の要素まで取得します

• mini：=miniのサブ配列[インデックス1から終了まで]

• p：=0

• res：=-inf

• p <ミニのサイズ、do

  • res：=resの最大値と（maxi [p] --mini [p]）

  • p：=p + 1

• 解像度を返す

例

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

def solve(nums):
   B = {}
   for i in range(len(nums)):
      x = nums[i]
      if x in B:
         B[x].append(i)
      else:
         B[x] = [i]

   mini = [float('inf')]
   maxi = [float('-inf')]
   for x in sorted(B.keys()):
      mini.append(min(mini[-1], min(B[x])))

   for x in sorted(B.keys(), reverse = True):
      maxi.append(max(maxi[-1], max(B[x])))

   maxi = maxi[::-1][:-1]
   mini = mini[1:]

   p = 0
   res = float('-inf')
   while p < len(mini):
      res = max(res, maxi[p] - mini[p])
      p += 1

   return res

nums = [6,0,8,2,1,5]
print(solve(nums))

入力

[6,0,8,2,1,5]

出力

4