Pythonで生成された配列の最大値を見つけるプログラム

数nがあるとします。次の方法で長さn+1の配列Aを生成する必要があります-

• A [0] =0

• A [1] =1

• A [2 * i] =A [i] if 2 <=2 * i <=n

• A [2 * i + 1] =A [i] + A [i + 1] if 2 <=2 * i + 1 <=n

最後に、配列numsで最大数を見つける必要があります。

したがって、入力がn =5の場合、出力は3になります。

• A [0] =0

• A [1] =1

• A [2] =A [1] =1

• A [3] =A [1] + A [2] =1 + 1 =2

• A [4] =A [2] =1

• A [5] =A [2] + A [3] =1 + 2 =3

• A [6] =A [3] =2

したがって、最大値は3です

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

• A：=0からnまでの新しいリスト

• Aの各要素iについて、実行します

  • iが0と同じか、iが1と同じ場合、

    • 次のイテレーションに進む

  • それ以外の場合、私が偶数の場合、

    • A [i]：=A[i/2の整数]

  • それ以外の場合

    • A [i]：=A[i/2の整数]+A [（i / 2の整数）+ 1]

• Aの最大要素を返す

例（Python）

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

def solve(n):
   A = list(range(0,n+1))
   for i in A:
      if i == 0 or i == 1:
         continue
      elif i%2 == 0:
         A[i] = A[i//2]
      else:
         A[i] = A[i//2] + A[(i//2) + 1]
   return max(A)

n = 5
print(solve(n))

入力

5

出力

3