Dãy số Wavio

def wavio_sequence(arr):
    n = len(arr)
    L = [1] * n
    R = [1] * n
 
    for i in range(1, n):
        for j in range(i):
            if arr[i] > arr[j]:
                L[i] = max(L[i], L[j] + 1)
 
    for i in range(n-2, -1, -1):
        for j in range(n-1, i, -1):
            if arr[i] > arr[j]:
                R[i] = max(R[i], R[j] + 1)
 
    res = 0
    for i in range(n):
        res = max(res, min(L[i], R[i]))
 
    return res * 2 - 1

Mã giả trên sử dụng mảng L và R để lưu trữ chiều dài của các dãy con tăng dần từ trái sang phải và các dãy con giảm dần từ phải sang trái của dãy số. Đầu tiên, vòng lặp đầu tiên sẽ tính toán chiều dài của các dãy con tăng dần bắt đầu từ mỗi phần tử của dãy số và lưu trữ vào mảng L. Tiếp theo, vòng lặp thứ hai sẽ tính toán chiều dài của các dãy con giảm dần kết thúc tại mỗi phần tử của dãy số và lưu trữ vào mảng R.

Sau khi tính toán được mảng L và R, ta sẽ duyệt qua các phần tử của dãy số và tính toán độ dài của dãy con tăng dần bắt đầu từ phần tử đó và độ dài của dãy con giảm dần kết thúc tại phần tử đó, và chọn dãy số có độ dài lớn nhất. Kết quả sẽ được trả về với độ dài của dãy số Wavio.

Ví dụ:

arr = [1, 3, 5, 3, 2, 4, 5, 7, 6, 4, 3]
print(wavio_sequence(arr)) # 5

Trong ví dụ này, dãy số nguyên dương là [1, 3, 5, 3, 2, 4, 5, 7, 6, 4, 3] và dãy số Wavio là [1, 3, 5, 4, 3], vì nó có thứ tự tăng dần ở nửa đầu và thứ tự giảm dần ở nửa sau. Kết quả trả về là 5, độ dài của dãy số Wavio này.

Cài đặt Dãy số Wavio với Thuật toán sử dụng Stack

Để cài đặt thuật toán sử dụng Stack để tìm dãy số Wavio của một dãy số nguyên dương, ta có thể sử dụng mã giả sau đây:

def wavio_sequence(arr):
    n = len(arr)
    L = [0] * n
    R = [0] * n
 
    # tính toán L[i], độ dài của dãy con tăng dần dài nhất bắt đầu từ arr[0] đến arr[i]
    stack = []
    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            stack.pop()
        if not stack:
            L[i] = i + 1
        else:
            L[i] = i - stack[-1]
        stack.append(i)
 
    # tính toán R[i], độ dài của dãy con giảm dần dài nhất kết thúc tại arr[i] 
    stack = []
    for i in range(n-1, -1, -1):
        while stack and arr[i] > arr[stack[-1]]:
            stack.pop()
        if not stack:
            R[i] = n - i
        else:
            R[i] = stack[-1] - i
        stack.append(i)
 
    res = 0
    for i in range(n):
        res = max(res, min(L[i], R[i]))
 
    return res * 2 - 1

Mã giả trên sử dụng hai stack để tính toán L và R, tương ứng với chiều dài của các dãy con tăng dần từ trái sang phải và các dãy con giảm dần từ phải sang trái của dãy số. Đầu tiên, vòng lặp đầu tiên sẽ tính toán L cho mỗi phần tử của dãy số bằng cách duyệt qua các phần tử của dãy số từ trái sang phải, và sử dụng stack để lưu trữ các chỉ số của các phần tử trong dãy con tăng dần dài nhất bắt đầu từ arr[0]. Mỗi khi thấy một phần tử arr[i] lớn hơn phần tử ở đỉnh của stack, ta loại bỏ phần tử đó và tính toán L[i] bằng cách lấy hiệu của chỉ số hiện tại i với chỉ số ở đỉnh của stack. Nếu stack rỗng, ta gán L[i] bằng i+1, tức dãy con tăng dần bắt đầu từ arr[0].

Tiếp theo, vòng lặp thứ hai sẽ tính toán R cho mỗi phần tử của dãy số bằng cách duyệt qua các phần tử của dãy số từ phải sang trái, và sử dụng stack để lưu trữ các chỉ số của các phần tử trong dãy con giảm dần dài nhất kết thúc tại arr[n-1]. Mỗi khi thấy một phần tử arr[i] lớn hơn phần tử ở đỉnh của stack, ta loại bỏ phần tử đó và tính toán R[i] bằng cách lấy hiệu của chỉ số ở đỉnh của stack với chỉ số hiện tại i. Nếu stack rỗng, ta gán R[i] bằng n-i, tức dãy con giảm dần kết thúc tại arr[n-1].

Cuối cùng, ta duyệt qua mỗi phần tử của dãy số và tính toán độ dài của dãy con Wavio bằng cách lấy giá trị nhỏ nhất của L[i] và R[i], và chọn giá trị lớn nhất trong tất cả các độ dài dãy con Wavio. Kết quả trả về là độ dài của dãy con Wavio nhân với 2 trừ đi 1.

Ví dụ, nếu ta có dãy số arr = [2, 1, 4, 3, 6, 5], ta sẽ tính toán L và R như sau:

L = [1, 1, 2, 2, 3, 3]
R = [3, 2, 2, 1, 1, 1]

Dựa trên L và R, ta tính toán độ dài của dãy con Wavio cho mỗi phần tử của dãy số như sau:

arr:    [2, 1, 4, 3, 6, 5]
L:      [1, 1, 2, 2, 3, 3]
R:      [3, 2, 2, 1, 1, 1]
Wavio:  [1, 1, 3, 3, 5, 5]

Độ dài của dãy con Wavio là 5, vì có thể lấy các dãy con Wavio có độ dài là 3 hoặc 5, ví dụ [2, 4, 6] hoặc [1, 4, 6, 5].

Kết luận

Dãy số Wavio là một dãy con của dãy số gốc mà trong đó các phần tử được sắp xếp theo thứ tự tăng dần rồi giảm dần. Vấn đề tìm độ dài của dãy số Wavio đã được giải quyết thông qua hai phương pháp chính là Quy hoạch động và Sử dụng stack.

Phương pháp Quy hoạch động là sử dụng bảng 2 chiều để lưu trữ thông tin về độ dài của các dãy con tăng dần và giảm dần bắt đầu từ mỗi phần tử của dãy số. Sau đó, ta duyệt qua mỗi phần tử và tính toán độ dài của dãy con Wavio bằng cách lấy giá trị nhỏ nhất của độ dài dãy con tăng dần và giảm dần. Cuối cùng, ta chọn giá trị lớn nhất trong tất cả các độ dài dãy con Wavio và trả về độ dài của dãy con Wavio nhân với 2 trừ đi 1.

Phương pháp sử dụng Stack là sử dụng stack để tính toán dãy con tăng dần và giảm dần bắt đầu từ mỗi phần tử trong dãy số. Sau đó, ta tính toán độ dài của dãy con Wavio cho mỗi phần tử dựa trên dãy con tăng dần và giảm dần bằng cách lấy giá trị nhỏ nhất của độ dài dãy con tăng dần và giảm dần. Cuối cùng, ta chọn giá trị lớn nhất trong tất cả các độ dài dãy con Wavio và trả về độ dài của dãy con Wavio nhân với 2 trừ đi 1.

Cả hai phương pháp đều có độ phức tạp thời gian là O(nlogn), với n là độ dài của dãy số. Tuy nhiên, phương pháp sử dụng Stack có thể tối ưu hơn đối với những trường hợp cụ thể, ví dụ như khi dãy số chỉ chứa các phần tử khác nhau.