Bài toán. Một dãy số có độ dài (số phần tử) là m được gọi là dãy hình nón nếu nó là một dãy gồm các số nguyên và cáo các đặc điểm sau:
- Số lượng phần tử của dãy là một số lẻ (hay m = 2*x +1)
- Không có hai số nào đứng cạnh nhau trong dãy có giá trị bằng nhau.
- x + 1 là số đầu tiên của một dãy tăng
- x + 1 số cuối cùng của dãy là một dãy giảm
Ví dụ: Dãy 3 6 9 5 2 là một dãy hình nón có độ dài bằng 5; dãy 1 8 3 6 9 không phải là dãy hình nón.
Cho dãy A gồm n số nguyên dương a1, a2, … an. Một dãy con của A là một dãy được tạo ra bằng cách lấy ra một số phần tử A nhưng giữ nguyên thứ tự (các phần tử có thể không liên tiếp nhau). Yêu cầu: Trong các dãy con của A hãy tìm độ dài của dãy con hình nón dài nhất?
Để giải quyết bài toán này, ta có thể sử dụng phương pháp quy hoạch động (đây là thuật toán tối ưu nhất) để tính toán độ dài của dãy con hình nón dài nhất. Cụ thể, ta sẽ tạo ra một mảng dp có độ dài bằng với số phần tử của dãy A, trong đó dp[i] sẽ là độ dài của dãy con hình nón dài nhất kết thúc tại vị trí i.
Với mỗi vị trí i, ta sẽ tính toán dp[i] bằng cách tìm kiếm tất cả các vị trí j < i và thỏa mãn điều kiện dp[j] > 0 (tức là tại vị trí j có một dãy hình nón kết thúc), sau đó kiểm tra xem dãy con bắt đầu từ vị trí j và kết thúc tại vị trí i có thể là một dãy hình nón không. Nếu có thể, ta cập nhật dp[i] bằng độ dài của dãy hình nón đó.
Cuối cùng, ta sẽ trả về giá trị lớn nhất trong mảng dp.
Dưới đây là code Python của thuật toán quy hoạch động này:
def is_cone_sequence(subseq):
n = len(subseq)
if n % 2 == 0:
return False
if any(subseq[i] == subseq[i+1] for i in range(n-1)):
return False
x = (n-1) // 2
if subseq[0] != x+1:
return False
if not all(subseq[i] > subseq[i+1] for i in range(x, n-1)):
return False
return True
def max_cone_sequence_length(A):
n = len(A)
dp = [0] * n
for i in range(n):
for j in range(i):
if dp[j] > 0 and is_cone_sequence(A[j:i+1]):
dp[i] = max(dp[i], i-j+1)
return max(dp)