C++. Các cao thủ giúp e bài 2 này với ạ.

Để giải bài toán này, chúng ta cần tìm chuỗi con dài nhất của dãy số cho trước sao cho dãy số đó "đẹp". Theo định nghĩa, một dãy số được gọi là đẹp nếu với mọi i < j, điều kiện P_i < P_j luôn đúng. Bài toán yêu cầu in ra độ dài của dãy số đẹp dài nhất.

Ta có thể sử dụng phương pháp lập trình động (Dynamic Programming) để giải quyết bài toán này. Cụ thể, chúng ta sẽ tạo một mảng động (DP) để lưu trữ độ dài của dãy số đẹp dài nhất kết thúc tại mỗi chỉ số.

1. Khởi tạo mảng DP: Mỗi phần tử DP[i] sẽ đại diện cho độ dài của dãy đẹp dài nhất cho đến chỉ số i, khởi đầu mọi phần tử của DP đều được gán giá trị 1 vì mỗi số đều có thể là một dãy số đẹp riêng lẻ.

2. Duyệt các phần tử của dãy số: Sử dụng hai vòng lặp lồng nhau:
- Vòng lặp ngoài sẽ lần lượt chọn từng phần tử như là điểm kết thúc của dãy con đẹp.
- Vòng lặp trong sẽ so sánh phần tử hiện tại với tất cả các phần tử trước đó để kiểm tra điều kiện P_i < P_j. Nếu điều kiện này thỏa mãn, ta có thể cập nhật giá trị của DP[hiện tại] như sau: DP[hiện tại] = max(DP[hiện tại], DP[trước đó] + 1).

3. Tìm giá trị lớn nhất trong mảng DP: Sau khi hai vòng lặp hoàn tất, giá trị lớn nhất trong mảng DP sẽ là độ dài của dãy số đẹp dài nhất.

Một điểm quan trọng cần lưu ý là độ phức tạp thời gian của giải pháp này là O(N^2), điều này có thể chấp nhận được bởi vì N ≤ 10^5 trong bài.

Cuối cùng, kết quả sẽ được ghi vào file DAYDEP.OUT. Đoạn mã nguồn dưới đây mô tả quy trình này bằng C++.

```cpp
#include
#include
#include
#include

int main() {
std::ifstream input("DAYDEP.INP");
std::ofstream output("DAYDEP.OUT");

int N;
input >> N;
std::vector arr(N);
for(int i = 0; i < N; i++) {
input >> arr[i];
}

std::vector DP(N, 1);

for(int i = 0; i < N; i++) {
for(int j = 0; j < i; j++) {
if(arr[j] < arr[i]) {
DP[i] = std::max(DP[i], DP[j] + 1);
}
}
}

int maxLength = *std::max_element(DP.begin(), DP.end());

output << maxLength;

return 0;
}
```

Giải pháp này sẽ cho phép bạn tìm ra độ dài của dãy số đẹp dài nhất một cách hiệu quả.