Gọi \(p[j]\) cho biết chỉ số \(i\) nhỏ nhất để đoạn \([i, j]\) ổn định, \(min[i, j]\): giá trị nhỏ nhất trong đoạn \([i, j]\), \(max[i, j]\): giá trị lớn nhất trong đoạn \([i, j]\).

Giả sử ta đã biết \(p[j-1]\)

• \(p[j]\) chỉ khác \(p[j-1]\) khi \((a[j] - min[p[j-1], j-1]) \gt T\) hoặc \((max[p[j-1], j-1] - a[j]) \gt T\).
• Nếu \(a[j-1] \gt a[j]\), ta cần lưu chỉ số dãy số giảm dần dài nhất có phần tử cuối là \(a[j]\).
• Nếu \(a[j-1] \lt a[j]\), ta cần lưu chỉ số dãy số tăng dần dài nhất có phần tử cuối là \(a[j]\).
• Nếu \(a[j-1] = a[j]\), ta cần chỉ cập nhật \(p[j] = p[j-1]\).

Xét ví dụ với dãy sau có \(T = 4\) và đoạn ổn định dài nhất hiện tại là \(4\)

Ta có:

• Dãy số giảm dần dài nhất là \(8, 7, 6, 5\) với các chỉ số tương ứng là \(4, 6, 8, 10\).
• Dãy số tăng dần dài nhất là \(4, 5\) với các chỉ số tương ứng là \(9, 10\).
• \(p[10] = 1\).

Nếu thêm \(a[11] = 2\), ta có:

• \(p[11] = 7\).
• Dãy số giảm dần dài nhất cập nhật lại là \(6, 5, 2\) với các chỉ số tương ứng là \(8, 10, 11\).
• Dãy số tăng dần dài nhất cập nhật lại là \(2\) với các chỉ số tương ứng là \(11\). Với hai dãy tăng/giảm dần này, ta có thể cập nhật lại \(p[j]\) một cách dễ dàng. Nhận thấy rằng những giá trị trong dãy giảm mà lớn hơn \(a[j]\) \(T\) đơn vị sẽ bị loại bỏ trong dãy mới và \(p[j]\) sẽ được cập nhật lại là \(p_1\) = [(chỉ số của phần tử cuối trong dãy giảm lớn hơn \(a[j]\) \(T\) đơn vị) + 1]. Xét tương tự cho dãy tăng để có \(p_2\) và \(p[j]\) mới = \(max(p_1, p_2)\).

Để giải bài toán này, chúng ta cần tìm số phiên giao dịch liên tiếp dài nhất mà chênh lệch giữa giá cao nhất và thấp nhất không vượt quá một ngưỡng T cho trước. Chúng ta sử dụng phương pháp sliding window kết hợp với hai deque để theo dõi giá trị lớn nhất và nhỏ nhất trong cửa sổ hiện tại một cách hiệu quả. Phương pháp tiếp cận

1. Sliding Window: Duy trì một cửa sổ trượt từ left đến right để xác định dãy con liên tiếp dài nhất thỏa mãn điều kiện chênh lệch giá.
2. Deque cho Max và Min: Sử dụng hai deque để theo dõi chỉ số của các phần tử có giá trị lớn nhất và nhỏ nhất trong cửa sổ hiện tại. Cấu trúc deque giúp duy trì các giá trị này một cách hiệu quả.
3. Cập nhật Deque: Khi mở rộng cửa sổ về bên phải, cập nhật deque để đảm bảo chúng luôn chứa các chỉ số của các phần tử có giá trị giảm dần (cho max deque) và tăng dần (cho min deque).
4. Kiểm tra điều kiện: Nếu chênh lệch giữa giá lớn nhất và nhỏ nhất vượt quá T, thu hẹp cửa sổ từ bên trái cho đến khi điều kiện được thỏa mãn.