#1342. SEQ - Dãy số

Bộ nhớ: 256 MiB Thời gian: 500 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: So sánh văn bản
Đưa lên bởi: Chùm CUỐI

Đề bài

ĐỀ KIỂM TRA ĐỘI TUYỂN HSG LẦN 1 - Ôn Hải Phòng T11/2020

Cho dãy a_1,a_2,…,a_n . Yêu cầu: Tìm Max{độ dài dãy con tăng chặt dài nhất, độ dài dãy con giảm chặt dài nhất, độ dài dãy con tăng chặt – giảm chặt dài nhất}

Dữ liệu vào:

  • Dòng đầu chứa số nguyên dương n\ (n≤10^5) ;
  • Dòng thứ hai chứa n số nguyên dương a_1,a_2,…,a_n\ (0≤a_i≤10^5, ∀1≤i≤n) .

Dữ liệu ra:

  • Ghi ra một số nguyên duy nhất là đáp án bài toán.

Ví dụ:

Dữ liệu vào:
4
2 1 5 3
Dữ liệu ra:
3
Giải thích:
  • Dãy con \{2,5,3\} hoặc \{1,5,3\} .
Dữ liệu vào:
3
1 5 5
Dữ liệu ra:
2
Giải thích:
  • Dãy con \{1,5\} .

Giới hạn:

  • 20\% số điểm có N≤1000 ;
  • 20\% số điểm khác có 1000<N≤5000 .