জেনারেটেড অ্যারেতে সর্বোচ্চ মান বের করা

একটি সংখ্যা 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

অ্যারেতে সর্বোচ্চ মান বের করতে হবে।

ইনপুট: n = 5 → আউটপুট: 3।

• A[0]=0, A[1]=1
• A[2]=A[1]=1
• A[3]=A[1]+A[2]=2
• A[4]=A[2]=1
• A[5]=A[2]+A[3]=3
• সর্বোচ্চ = ৩

সমাধানের ধাপসমূহ

• A := list(range(n+1))

• প্রতিটি i ∈ A-এর জন্য:

  • যদি i == 0 বা 1: continue
  • যদি i জোড়: A[i] = A[i//2]
  • অন্যথায়: A[i] = A[i//2] + A[i//2 + 1]

• max(A) রিটার্ন করুন

উদাহরণ (Python)

def solve(n):
    A = list(range(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