Dãy Con Đơn Điệu Tăng Dài Nhất Trong Python

Dãy con đơn điệu tăng dài nhất là một bài toán kinh điển trong lập trình. Tham khảo một bài toán dưới đây:

Cho dãy số nguyên A gồm n phần tử, nằm trong khoảng từ -10000 đến 10000. Nhiệm vụ của bạn là tìm dãy con đơn điệu tăng dài nhất của dãy A, bắt đầu từ phần tử đầu tiên (a1).

Yêu Cầu: Hãy viết một chương trình để thực hiện việc sau:

1. Tìm độ dài của dãy con đơn điệu tăng dài nhất của dãy A.
2. Liệt kê các phần tử của dãy con tăng này.

Đầu Vào

• Dòng đầu tiên chứa một số nguyên dương N (1 ≤ N ≤ 1000) – số phần tử của dãy A.
• Dòng thứ hai chứa N số nguyên a1, a2, …, an (-10000 ≤ ai ≤ 10000) các phần tử của dãy A, cách nhau bởi ít nhất một dấu cách.

Đầu Ra

Ghi vào tệp văn bản SEQ.OUT theo cấu trúc sau:

• Dòng 1: Ghi độ dài của dãy con đơn điệu tăng dài nhất của dãy A.
• Dòng 2: Ghi các phần tử của dãy con tăng này, cách nhau bởi ít nhất một dấu cách.

Ví dụ:

Giải Thích

Dãy con đơn điệu tăng dài nhất bắt đầu từ a1 là {1, 2, 5, 6, 8} có độ dài là 5.

Dưới đây là một đoạn mã Python để giải bài toán tìm dãy con đơn điệu tăng dài nhất của dãy số nguyên A:

# Đọc dữ liệu từ tệp SEQ.INP
with open("SEQ.INP", "r") as file:
    n = int(file.readline())
    arr = list(map(int, file.readline().split()))

# Khởi tạo mảng dp để lưu độ dài của dãy con tăng tại mỗi vị trí
dp = [1] * n

# Khởi tạo mảng truy vết để lưu vị trí trước đó của phần tử trong dãy con tăng dài nhất
prev = [-1] * n

# Tìm độ dài của dãy con đơn điệu tăng dài nhất và vị trí kết thúc của nó
max_length = 1
end_index = 0

for i in range(1, n):
    for j in range(i):
        if arr[i] > arr[j] and dp[i] < dp[j] + 1:
            dp[i] = dp[j] + 1
            prev[i] = j
        if dp[i] > max_length:
            max_length = dp[i]
            end_index = i

# Xây dựng dãy con đơn điệu tăng dài nhất
longest_increasing_seq = []
index = end_index
while index >= 0:
    longest_increasing_seq.append(arr[index])
    index = prev[index]

# Đảo ngược dãy con để có thứ tự tăng từ a1
longest_increasing_seq.reverse()

# Ghi kết quả vào tệp SEQ.OUT
with open("SEQ.OUT", "w") as file:
    file.write(str(max_length) + "\n")
    file.write(" ".join(map(str, longest_increasing_seq)))

Trong đoạn mã này, chúng ta sử dụng mảng dp để lưu độ dài của dãy con tăng tại mỗi vị trí và mảng prev để lưu vị trí trước đó của phần tử trong dãy con tăng dài nhất. Chúng ta duyệt qua mỗi phần tử của dãy A và kiểm tra xem nó có thể được thêm vào dãy con tăng tại vị trí đó không. Sau đó, chúng ta tìm độ dài lớn nhất và vị trí kết thúc của dãy con tăng dài nhất. Cuối cùng, chúng ta xây dựng lại dãy con đơn điệu tăng dài nhất và ghi kết quả vào tệp “SEQ.OUT”.

Để hiểu rõ hơn về thuật toán. Hãy xem xét một ví dụ cụ thể để hiểu cách thuật toán hoạt động. Cho dãy số nguyên A sau đây:

A = [1, 3, 5, 2, 6, 4, 8, 7]

Chúng ta sẽ sử dụng thuật toán để tìm dãy con đơn điệu tăng dài nhất bắt đầu từ a1, tức là từ số 1.

Bước 1: Khởi tạo mảng dp và prev:

dp = [1, 1, 1, 1, 1, 1, 1, 1] # Độ dài của dãy con tăng tại mỗi vị trí
prev = [-1, -1, -1, -1, -1, -1, -1, -1] # Vị trí trước đó của phần tử trong dãy con tăng dài nhất

Bước 2: Duyệt qua từng phần tử của dãy A để tính dp và prev:

• a2 = 3: Chúng ta không có phần tử nào nhỏ hơn 3 trong dãy con tăng tại a1 = 1, vì vậy dp[2] vẫn bằng 1.
• a3 = 5: Chúng ta có a2 = 3 nhỏ hơn 5, vì vậy dp[3] được cập nhật thành dp[2] + 1 = 2, và prev[3] được cập nhật thành 2 (nghĩa là ở vị trí 3, phần tử 5 được kết nối với phần tử 3).
• a4 = 2: Chúng ta không có phần tử nào nhỏ hơn 2 trong dãy con tăng tại a1 = 1, vì vậy dp[4] vẫn bằng 1.
• a5 = 6: Chúng ta có a3 = 5 nhỏ hơn 6, vì vậy dp[5] được cập nhật thành dp[3] + 1 = 3, và prev[5] được cập nhật thành 3 (nghĩa là ở vị trí 5, phần tử 6 được kết nối với phần tử 5).
• a6 = 4: Chúng ta không có phần tử nào nhỏ hơn 4 trong dãy con tăng tại a1 = 1, vì vậy dp[6] vẫn bằng 1.
• a7 = 8: Chúng ta có a6 = 4 nhỏ hơn 8, vì vậy dp[7] được cập nhật thành dp[6] + 1 = 2, và prev[7] được cập nhật thành 6 (nghĩa là ở vị trí 7, phần tử 8 được kết nối với phần tử 4).
• a8 = 7: Chúng ta có a7 = 8 nhỏ hơn 7, vì vậy dp[8] được cập nhật thành dp[7] + 1 = 3, và prev[8] được cập nhật thành 7 (nghĩa là ở vị trí 8, phần tử 7 được kết nối với phần tử 8).

Bước 3: Tìm độ dài lớn nhất và vị trí kết thúc của dãy con tăng dài nhất:

Trong trường hợp này, độ dài lớn nhất là 3, và vị trí kết thúc là 8 (phần tử 7).

Bước 4: Xây dựng lại dãy con đơn điệu tăng dài nhất:

Chúng ta bắt đầu từ vị trí kết thúc 8 và theo dấu vết prev để xây dựng lại dãy con:

• a8 = 7 được thêm vào dãy con.
• a7 = 8 được thêm vào dãy con.
• a6 = 4 được thêm vào dãy con.

Dãy con đơn điệu tăng dài nhất là [4, 7, 8].

Bước 5: Ghi kết quả vào tệp SEQ.OUT:

3
4 7 8

Đây là dãy con đơn điệu tăng dài nhất của dãy A, và độ dài của nó là 3.