Pythonで特定のルールに従って生成した配列の最大値を求めるプログラム

この記事では、特別なルールに従って生成された配列の中から最大値を求めるPythonプログラムを解説します。

問題の概要

ある整数 n が与えられたとします。このとき、次のルールに従って長さ n + 1 の配列 A を生成することを考えます。

• A[0] = 0
• A[1] = 1
• A[2 * i] = A[i]（2 ≤ 2 * i ≤ n の場合）
• A[2 * i + 1] = A[i] + A[i + 1]（2 ≤ 2 * i + 1 ≤ n の場合）

つまり、偶数番目の要素は半分のインデックスの値をそのままコピーし、奇数番目の要素は隣り合う2つの要素の和になるという再帰的な定義です。

最終的なゴールは、生成された配列 A の中から最大値を見つけることです。

具体例

入力が 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 であるため、答えは 3 となります。

解法のアプローチ

この問題は、次の手順で解くことができます。

• 0 から n までの連続した整数を含むリスト A を作成する。
• A の各要素 i について以下を繰り返す。
  • i が 0 または 1 の場合は、初期値が定義済みなので次の反復へ進む。
  • i が偶数の場合：A[i] := A[i ÷ 2 の整数部分]
  • i が奇数の場合：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

計算量について

このアルゴリズムは、配列の各要素を一度ずつ処理するため、時間計算量は O(n)、配列を保持するために空間計算量も O(n) となります。n が大きくなっても効率的に動作するシンプルな解法です。