#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <iomanip>
#include <climits>
#include <cstdlib>
#include <map>
#include <unordered_set>
using std::cin, std::cout, std::endl, std::string, std::min;
int main()
{
int n;
cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
std::vector<int> pref_min(n, 0);
std::vector<int> suf_min(n, n - 1);
std::vector<int> pref_max(n, 0);
std::vector<int> suf_max(n, n - 1);
for (int i = 1; i < n; i++) {
if (a[i] < a[pref_min[i - 1]]) {
pref_min[i] = i;
} else {
pref_min[i] = pref_min[i - 1];
}
if (a[i] > a[pref_max[i - 1]]) {
pref_max[i] = i;
} else {
pref_max[i] = pref_max[i - 1];
}
}
for (int i = n - 2; i >= 0; i--) {
if (a[i] <= a[suf_min[i + 1]]) {
suf_min[i] = i;
} else {
suf_min[i] = suf_min[i + 1];
}
if (a[i] >= a[suf_max[i + 1]]) {
suf_max[i] = i;
} else {
suf_max[i] = suf_max[i + 1];
}
}
int best_i_1 = 0, best_j_1 = 1;
int best_i_2 = 0, best_j_2 = 1;
for (int i = 1; i < n; i++) {
if (a[best_i_1] - a[best_j_1] > a[pref_min[i - 1]] - a[suf_max[i]]) {
best_i_1 = pref_min[i - 1];
best_j_1 = suf_max[i];
}
if (a[best_i_2] - a[best_j_2] < a[pref_max[i - 1]] - a[suf_min[i]]) {
best_i_2 = pref_max[i - 1];
best_j_2 = suf_min[i];
}
}
cout << best_i_1 + 1 << " " << best_j_1 + 1 << endl << best_i_2 + 1 << " " << best_j_2 + 1 << endl;
}
1) Этот код находит две пары индексов в массиве: одну с максимальной разностью между минимальным элементом в префиксе и максимальным в суффиксе, и другую с максимальной разностью между максимальным элементом в префиксе и минимальным в суффиксе.
2) Подсказки:
- Обрати внимание на то, как заполняются массивы `pref_min`, `pref_max`, `suf_min` и `suf_max` — они хранят индексы минимальных и максимальных элементов на префиксах и суффиксах.
- В основном цикле сравниваются разности элементов, чтобы найти оптимальные пары индексов. Убедись, что понимаешь логику сравнения и обновления `best_i_1`, `best_j_1`, `best_i_2` и `best_j_2`.