Sub 2:

Gọi \(p[i]\) là vị trí mà \(b[p[i]] = a[i]\). Giả sử dãy con chung dài nhất của 2 dãy có dạng sau:

• \(a[i_1], a[i_2], ..., a[i_l]\)
• \(b[p[i_1]], b[p[i_2]], ..., b[p[i_l]]\)

Điều kiện của dãy con là:

• \(i_1 < i_2 < ... < i_l\)
• \(p[i_1] < p[i_2] < ... < p[i_l]\)

Nói cách khác, đây chính là dãy tăng của \(p\). Bài toán LIS có thể được giải quyết trong \(O(n \log n)\)

Sub 3:

Ta cần tổng quát ý tưởng sub 2. Điểm khác biệt là \(p[i]\) không còn xác định duy nhất với mỗi \(i\). Giả sử 2 dãy con chung có dạng sau:

• \(a[i_1], a[i_2], ..., a[i_l]\)
• \(b[j_1], b[j_2], ..., b[j_l]\)

Điều kiện dãy con là:

• \(i_1 < i_2 < ... < i_l\)
• \(j_1 < j_2 < ... < j_l\)
• \(a[i_m] = b[j_m]\) với mọi \(m\)

Để ý rằng số lượng bộ \((i_m, j_m)\) có thể có là không nhiều, chính xác là \(nk^2\). Như vậy, ta có thể liệt kê tất cả cặp \((i, j)\) thỏa mãn \(a[i] = b[j]\). Bài toán quy về tìm số cặp nhiều nhất sao cho:

• \(i_1 < i_2 < ... < i_l\)
• \(j_1 < j_2 < ... < j_l\)

Bài toán có thể được giải bằng LIS như sau. Sort tất cả cặp \((i, j)\) theo thứ tự tăng dần của \(i\). Nếu \(i\) bằng nhau thì sort theo thứ tự giảm dần của \(j\). Code C++ nhìn như sau:

bool cmp(pair<int, int> a, pair<int, int> b) {
  if (a.first == b.first) return a.second > b.second;
  return a.first < b.first;
}
sort(v.begin(), v.end(), cmp);

Lúc này ta có dãy \((i_1, j_1), (i_2, j_2), ...\) sắp xếp theo thứ tự tăng dần của \(i\). Đáp số là LIS của dãy \(j_1, j_2, ...\).

Bonus: Hãy giải thích tại sao khi \(i\) bằng nhau, ta phải sort theo thứ tự giảm dần của \(j\)?