Trộm nhà không liền kề
Points
25
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Một dãy phố có $N$ ngôi nhà xếp thành một hàng ngang, ngôi nhà thứ $i$ có số tiền là $A_i$. Một tên trộm muốn lấy được tổng số tiền lớn nhất nhưng hệ thống báo động sẽ kích hoạt nếu hai ngôi nhà liền kề nhau cùng bị trộm.
Hãy tính số tiền lớn nhất tên trộm có thể lấy được.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên không âm $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 10^9$).
Dữ liệu ra
Một số nguyên duy nhất là tổng số tiền lớn nhất.
Ví dụ
| Input | Output |
|---|---|
4<br>1 2 3 1 |
4 |
Giới hạn
- $1 \le N \le 10^5$
- $0 \le A_i \le 10^9$
Community Discussion