Subsequence là gì?

Một dãy con (subsequence) là một dãy (sequence) có thể được dẫn xuất từ một dãy khác bằng cách loại bỏ không hoặc nhiều phần tử, mà không thay đổi thứ tự của các phần tử còn lại. Ví dụ xét mảng [1, 2, 3, 4] có 15 dãy con. Đó là (1), (2), (3), (4), (1,2), (1,3), (1,4), (2,3), (2,4), (3 , 4), (1,2,3), (1,2,4), (1,3,4), (2,3,4), (1,2,3,4). Tổng quát hơn, chúng ta có thể nói rằng đối với một dãy có kích thước n, chúng ta có thể có tổng cộng (2n-1) dãy con (subsequence) không rỗng.