Ta có một cách dp như sau: \(dp(n + 1) = 1\), \(dp(i) = \sum_{j = i}^{n} dp(j + 1)\) với đoạn \([i, j]\) có ít nhất \(k\) giá trị phân biệt.

Vậy cách làm này hoạt động trong \(O(n ^ 2)\), để tối ưu ta có nhận xét: Nếu đoạn \([l, r]\) có ít nhất \(k\) giá trị phân biệt thì đoạn \([l, r + 1]\) cũng có ít nhất \(k\) giá trị phân biệt. Ta sẽ tính \(dp(i)\) từ \(n\) về \(1\). Giả sử ta chọn đoạn có \(l = i\), ta cần tìm vị trí \(r\) nhỏ nhất sao cho \([l, r]\) có ít nhất \(k\) giá trị phân biệt và gọi nó là \(pos\), vậy \(dp(i) = \sum_{j = pos}^{n} dp(j + 1)\) còn công việc tính tổng các phần tử trong mảng dp thuộc đoạn \([pos + 1, n + 1]\) có thể được thực hiện đơn giản bằng mảng tổng dồn. Việc tìm vị trí \(r\) đầu tiên thoả mãn ta sẽ làm như sau: Xét các giá trị trong đoạn \([i, n]\), và ta đánh dấu phần tử với giá trị \(a_j\) (\(a_j\) xuất hiện đầu tiên trong \([i, n]\) tại vị trí \(j\)) với giá trị là \(1\), các phần tử khác ta đánh dấu là \(0\). Bây giờ việc xem thử một đoạn \([i, j]\) có bao nhiêu phần tử phân biệt có thể được thực hiện đơn giản bằng một cấu trúc dữ liệu hỗ trợ việc tính tổng và cập nhật một cách nhanh chóng (fenwick tree hoặc segment tree) và sau đấy ta có thể sử dụng kĩ thuật chặt nhị phân trên fenwick tree hoặc trên segment tree để tìm vị trí \(r\) đầu tiên sao cho \([i, r]\) có ít nhất \(k\) phần tử phân biệt.