# Lời giải bài Beads

## Tác giả: Phạm Quang Minh, I2023

## 1. Tóm tắt đề
Cho dãy $a$ có $n$ $(1 \le n \le 10^5)$ phần tử, hãy tìm dãy con tăng dài nhất bằng cách thêm phần tử $a_i$ hiện tại theo 1 trong 2 cách:
1. thêm phần tử $a_i$ vào đầu dãy con tăng hiện tại.
1. thêm phần tử $a_i$ vào cuối dãy con tăng hiện tại.

## 2. Nhận xét bài toán

- Ta có thể thấy được để thực hiện 1 trong 2 cách thêm phần tử cũng tương đương với việc tìm dãy con tăng dần dài nhất hoặc dãy con giảm dần dài nhất.
- Để thực hiện cả 2 thao tác, ta có nhận xét là ta sẽ chọn 1 dãy con tăng dài nhất và 1 dãy con giảm dài nhất sao cho chúng không giao nhau.
- Để tìm 1 dãy con tăng và 1 dãy con giảm không giao nhau, ta cần tìm một dãy con tăng dần bắt đầu với phần tử có giá trị là $x$ và một dãy con giảm bắt đầu với phần tử có giá trị là $x-1$ $(1 \leq x \leq 10^9)$.
- Để giảm số lượng $x$ cần xét, ta nhận xét là chỉ có thứ tự tương đối của các phần tử $a_i$ quan trọng, từ đó ta có thể sử dụng [kĩ thuật nén số](https://usaco.guide/silver/sorting-custom), khi đó chỉ cần xét $x$ $(1 \leq x \leq n)$.
- Độ phức tạp: $O(n^2)$

## 3. Cải tiến
- Để tìm dãy con tăng hoặc giảm dần một cách nhanh chóng, ta có thể sử dụng [cấu trúc dữ liệu hoặc chặt nhị phân](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html).

### Độ phức tạp: $O(n \times log(n))$

### Code mẫu: [Link](https://ideone.com/RCIbEC)
### Tag: Dynamic Programming, Data Structure