# LIS DP in a nutshell
**in a nutshell = ultra-oversimplified**
###### Author: zeena (i2225 PTNK)
###### Resources: [cp-algorithms](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html)
:::success
:bulb: Mình **khuyến khích** bạn nên đọc song song shitpost này và tài liệu mình liệt kê ở trên.
:::

---
## wtf is DP?
read [this shit](https://usaco.guide/gold/intro-dp?lang=cpp)

## wut is LIS?
LIS (Longest Increasing Subsequence) là một trong những dạng DP khá kinh điển. Như cái tên, LIS là dãy con đơn điệu tăng dài nhất.

**Ví dụ:** cho mảng $A =$ $[1, 5, 2, 4, 2]$, thì LIS là $[1, 2, 4]$ và nó có độ dài là 3.

## how does it work?
Cho bài toán kinh điển: [VNOJ](https://oj.vnoi.info/problem/liq)

Ta gọi $f(i)$ là độ dài LIS với phần tử kết thúc cuối cùng thuộc vị trí $i$.
Nhận xét: Với mỗi $i$ đang xét, ta cần phải tìm các phần tử có vị trí $j$ từ $1$ tới $i-1$ sao cho $A_j < A_i$.

Khi đấy, ta sẽ lấy $f(i)=$ $\max\limits_{j = 1, A_j<A_i}^{i-1} {(f(j)+1)}$

:::spoiler Implementation (C++)

int dp[n+1] = {};
dp[1] = 1;
int LIS = 1;

for (int i=2; i<=n; ++i) {
    for (int j=1; j<i; ++j) {
        if (a[i]>a[j]) dp[i] = max(dp[i], dp[j]+1);
    }
    LIS = max(LIS, dp[i]);
}
return LIS;

:::

Độ phức tạp cuối cùng sẽ là $O(n^2)$.

## xtension
Bây giờ, ta nâng $n$ lên, cho đến khi nào cách cũ bị **TLE** thì thôi.
[Cũng là VNOJ](https://oj.vnoi.info/problem/lis)

### "Tham Lam"
Ta có thể lấy mảng $dp$ là 1 mảng chứa LIS.
$dp$ ban đầu chỉ có phần tử $A_1$.

Với mọi $i$ $(1 < i \le n)$, ta sẽ tìm vị trí $j$ nhỏ nhất trong $dp$ sao cho $dp_j \ge A_i$.

Do vậy ta sẽ có 2 trường hợp:
- Nếu có: đặt phần tử $A_i$ ở vị trí tìm được trong mảng $dp$.
- Nếu không có: ta thêm vào mảng $dp$ từ sau cùng.

Từ đấy ta có nhận xét như sau:
- Mảng $dp$ luôn chứa các phần tử được xếp tăng dần. $(*)$
- Nhờ vào $(*)$, ta có thể chặt nhị phân trong mảng $dp$ để kiểm tra.

:::spoiler Vì sao mình lại làm như vậy?
**"Tham lam"**
:::
<br />

:::spoiler Implementation (C++)

vector<int> dp;
dp.push_back(a[1]);
for (int i=2; i<=n; i++) {
    auto j = lower_bound(dp.begin(), dp.end(), a[i]);
    if (j==dp.end()) dp.push_back(a[i]);
    else *j = a[i];
}
return dp.size();

:::
<br />

**Lưu ý:** Có một số biến thể của LIS sẽ có một số trường hợp cách này không giải được mà ta sẽ phải dùng CTDL để giải.

### Dùng CTDL
Quay về cách đầu tiên, ta thấy $f(i) = f(j) + 1$ với điều kiện là $A_j < A_i$.
Như vậy, ta sẽ gọi 1 mảng $t$ nào đó sao cho $t[A_i] = f(i)$.

Khi đấy, bài toán để tìm $f(i)$ trở thành bài toán trở thành tìm $\max$ của mảng $t$ trong đoạn $[1, A_i)$ (tùy vào giới hạn bé nhất của $A_i$).

Dễ dàng nhận thấy, ta có thể quản lý hiệu quả và truy cập nhanh đoạn này bằng CTDL như Fenwick Tree, Segment Tree...

:::spoiler Fenwick Tree Implementation (FPC)

var	
    bit: array[1..100005] of longInt;
    n, i, a: longInt;

function max(a, b: longInt): longInt;
begin
if (a<b) then exit(b)
else exit(a)
end;

procedure upd(x, v: longInt);
begin
while (x <= n) do
    begin
        bit[x] := max(bit[x], v);
        inc(x, x and -x);
    end;
end;

function query(x: longInt): longInt;
var res: longInt;
begin
res := 0;
while (x > 0) do  
    begin
        res := max(res, bit[x]);
        dec(x, x and -x)
    end;
exit(res)
end;


begin
readln(n);
for i := 1 to n do
    begin
        read(a);
        upd(a, query(a)+1);
    end;
writeln(query(n));
end.

:::
<br />

**Lưu ý:** Cách này chỉ dùng được khi giới hạn của $A_i$ không vượt quá khoảng $10^7$.
Do đó mà cách này không thể dùng được cho bài trên của VNOJ.

Độ phức tạp cuối cùng của cả 2 cách trên sẽ là $O(n.log(n))$.