Задача с собеседования в Т-банк

Условие:
Определим понятие хорошей последовательности - абсолютная разница между любыми двумя элементами этой последовательности должна быть больше либо равна максимальному элементу. То есть (i, j) | a_i - a_j | > max(a[l:r+1]). Вам даётся массив длины 10^5 и требуется определить наибольшую длину хорошей подпослдеовательности.

наш чат алгоритмистов

Решение:
Очевидно, что если в подпоследовательности будет больше двух положительных элементов, то x - y > x (x = max(x, y)) верно лишь в том случае, когда y < 0. Соответственно длина последовательности будет точно хотя бы равняться количеству отрицательных элементов. При построении последовательности возьмем один положительный элемент (потому что иначе с двумя положительными не будет выполняться условие |a_i - a_j| > max(a_i, a_j) и возьмем жадно аименьший положительный. Тогда можно будет проверить, получится ли этот положительный элемент добавить в последовательность отрицательных так чтобы не нарушалось то условие (для этого достаточно перебрать наименьшую абсолютную разницу, то есть просто перебрать пары соседних в отсортированном порядке).


int n;
cin >> n;
vector<int> a(n);
int ans = 0;
for (int i = 0; i < n; i++ ){
cin >> a[i];
ans += (a[i] <= 0);
}
sort(a.begin(), a.end());
int mn = inf;
for (int i = 0; i < n; i++) {
if (a[i] > 0) {
mn = min(a[i], mn);
}
}
bool flag = (mn != inf);
for (int i = 1; i < n; i++) {
if (a[i] <= 0) {
flag &= (a[i] - a[i - 1] >= mn)
}
}
cout << ans + flag;

@algoses