Dãy con
Xem dạng PDF
Gửi bài giải
Điểm:
0,01 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
1G
Input:
BAI1.INP
Output:
BAI1.OUT
Tác giả:
Nguồn bài:
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch
Cho một số nguyên dương ~n~ và dãy gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~. Một dãy con không kề nhau là dãy được tạo ra bằng cách chọn ra một số phần tử của dãy sao cho không có hai phần tử nào được chọn có vị trí ban đầu kề nhau.
Hãy chọn ra một dãy con không kề nhau sao cho thỏa mãn hai điều kiện sau:
- Tổng các phần tử được chọn là một số lẻ;
- Tổng các phần tử được chọn là lớn nhất có thể.
Input BAI1.INP
- Dòng 1: chứa số nguyên dương ~n~ (~1 \le n \le 10^5~).
- Dòng 2: chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ (~1 \le a_i \le 10^9~).
Output BAI1.OUT
In ra một số nguyên là tổng lẻ lớn nhất tìm được. Nếu không tìm được dãy con thỏa mãn, in ~-1~.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | 25% | ~n \le 20~ |
| 2 | 35% | ~n \le 2000~, ~a_i \le 1000~ |
| 3 | 40% | Không có ràng buộc bổ sung |
Sample Input 1
5
2 3 4 5 1
Sample Output 1
7
Notes
Chọn dãy ~\{2, 4, 1\}~ (các phần tử ở vị trí 1, 3 và 5) có tổng 7 là số lẻ và không có hai phần tử được chọn nào kề nhau. Đây là dãy có tổng lớn nhất thỏa mãn.
Đang tải...