Dãy Con Tăng Dài Nhất Khi Đổi 1 Phần Tử
Points
75
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Đề bài
Cho dãy số nguyên $A$ gồm $N$ phần tử. Bạn được phép chọn tối đa một phần tử trong dãy và thay đổi giá trị của nó thành một số nguyên bất kỳ. Hãy tìm độ dài lớn nhất có thể của dãy con tăng nghiêm ngặt sau khi thực hiện thao tác trên.
Dữ liệu vào
- Dòng đầu: số nguyên dương $N$ $(1 \le N \le 10^5)$.
- Dòng thứ hai: $N$ số nguyên $a_1, a_2, \ldots, a_N$ $(|a_i| \le 10^9)$.
Dữ liệu ra
- In ra độ dài lớn nhất của dãy con tăng nghiêm ngặt.
Ví dụ
| Input | Output |
|---|---|
| 6\n1 2 10 4 5 6 | 6 |
| 5\n5 4 3 2 1 | 2 |
Giới hạn
- $1 \le N \le 10^5$
- $|a_i| \le 10^9$
- Thời gian: 1 giây
- Bộ nhớ: 256 MB
Community Discussion