Dãy đẹp
Xem dạng PDF
Gửi bài giải
Điểm:
5,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Hôm nay, các bạn nhỏ ABC Smart lại được Thầy giáo đố một bài toán sau: Cho một dãy số nguyên ~𝑎_1, 𝑎_2, . . . , 𝑎_𝑛~. Các phần tử trong dãy được sắp xếp theo trình tự tăng dần, tức là ~𝑎_𝑖 ≤𝑎_{𝑖+1}~ với mọi ~1 ≤ 𝑖 < 𝑛~. Ta định nghĩa độ đẹp của dãy ~~𝑎 là khoảng cách lớn nhất giữa hai phần tử liên tiếp bất kì trong dãy. Nói cách khác, độ đẹp của dãy 𝑎 là giá trị ~𝑎_𝑖 – 𝑎_{i-1}~ lớn nhất với mọi 2 ≤ 𝑖 ≤ 𝑛.
Yêu cầu: Hãy xoá một phần tử bất kì trong dãy ~𝑎~ sao cho độ đẹp của dãy nhận được là lớn nhất có thể.
Dữ liệu vào:
- Dòng đầu tiên là số nguyên dương ~𝑛~ (~3 ≤ 𝑛 ≤ 10^6~);
- Dòng thứ hai chứa 𝑛 số nguyên dương ~𝑎_1, 𝑎_2, . . . , 𝑎_𝑛~ (~𝑎_𝑖 ≤ 2 × 10^9~).
Kết quả:
- Ghi một số nguyên là độ đẹp của dãy sau khi đã xoá 1 phần tử.
Ví dụ
Input
4
2 4 5 6
Output
3
Giải thích:
- Ta xoá đi phần tử thứ 2 của dãy, thì được dãy là 2, 5, 6. Suy ra độ đẹp bằng 3.
Bình luận
include <bits/stdc++.h>
using namespace std; int main() { int n; cin >> n; vector<long long> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } long long k = 0; for (int i = 1; i < n - 1; i++) { long long d = max(a[i + 1] - a[i - 1], k); k = max(d, k); } cout << k; return 0; }