โปรแกรมหาค่าสูงสุดในอาร์เรย์ที่สร้างขึ้นใน Python

สมมติว่าเรามีตัวเลข n เราต้องสร้างอาร์เรย์ A ที่มีความยาว n + 1 ด้วยวิธีต่อไปนี้ -

• 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

สุดท้ายเราต้องหาจำนวนสูงสุดในอาร์เรย์ 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

• สำหรับแต่ละองค์ประกอบ i ใน A ทำ

  • ถ้าฉันเหมือนกับ 0 หรือฉันเหมือนกับ 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