Dãy Con Tăng Dài Nhất Khi Đổi 1 Phần Tử

Binary-search Dynamic Programming
Points
75
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
dp
Submissions
Đề 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
Draft saved