Vì độ dài dãy con chỉ phụ thuộc vào một yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi $L_i$ là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ $A_1$ đến $A_i$ và phần tử cuối cùng là $A_i$.
Nhận xét với cách làm này ta đã chia 1 bài toán lớn [dãy con của $n$ số] thành các bài toán con cùng kiểu có kích thước nhỏ hơn [dãy con của dãy $i$ số]. Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con.
Ta có công thức QHĐ để tính $L_i$ như sau:
- $L_1 = 1$. [Hiển nhiên]
- $L_i = max[1, L_j + 1]$ với mọi phần tử $j$ thỏa mãn: $0