Chương trình tìm giá trị lớn nhất trong mảng sinh ra trong Python

Giả sử ta có số n. Tạo mảng A độ dài n+1:

• A[0] = 0
• A[1] = 1
• A[2*i] = A[i] nếu 2 <= 2*i <= n
• A[2*i+1] = A[i] + A[i+1] nếu 2 <= 2*i+1 <= n

Tìm số lớn nhất trong mảng A.

Ví dụ: n = 5, kết quả 3 vì A = [0,1,1,2,1,3], max = 3.

Giải thuật

1. A := list(range(0, n+1))
2. Với mỗi i trong A:
   • Nếu i == 0 or i == 1: continue
   • Ngược lại nếu i chẵn: A[i] = A[i//2]
   • Ngược lại: A[i] = A[i//2] + A[i//2 + 1]
3. Trả về max(A)

Ví dụ (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))

Input

5

Output

3