Pythonで1つのリストの最大のk番目のインデックス値を見つけるプログラム

n、total、およびkの3つの値があるとします。ここで、合計が合計と同じで、任意の2つの連続する要素間の絶対差が最大1であるサイズnのリストについて考えます。このようなリストのインデックスkで最大値を見つける必要があります。

したがって、入力がn=5合計=15k =3の場合、出力は4になります。これは、1つの可能なリストが[3,2,3,4,3]のようであり、インデックス3で見つかる最大要素であるためです。は4です。

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

• x：=0
• 次のことを繰り返し行います。
  • a：=k + 1
  • s：=（x + x --a + 1）* a/2の場合はフロア
  • a：=n-k
  • s：=s +（x + x --a + 1）* a/2のフロア
  • s：=s-x
  • 合計の場合、
    • ループから抜け出す
  • x：=x + 1
• return x-1

例

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

def solve(n, total, k):
   x = 0
   while 1:
      a = k + 1
      s = (x + x - a + 1) * a // 2
      a = n - k
      s += (x + x - a + 1) * a // 2
      s -= x
      if s > total:
         break
      x += 1
   return x - 1

n = 5
total = 15
k = 3
print(solve(n, total, k))

入力

5, 15, 3

出力

4