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,a[1000005]; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; int max1=-1; for(int i=3;i<=n;i++) { int z=a[i]-a[i-2]; if(max1<z)max1=z; } cout<<max1; return 0; }