Массив A [] содержит только '1' и '-1'
Построить массив B, где B [i] - длина самого длинного непрерывного подмассива, начинающегося с j и заканчивающегося на i, где j < i and A[j] + .. + A[i] > 0
Очевидное решение O (n ^ 2) будет:
for (int i = 0; i < A.size(); ++i) {
j = i-1;
sum = A[i];
B[i] = -1; //index which fills criteria not found
while ( j >=0 ) {
sum += A[j];
if (sum > 0)
B[i] = i - j + 1;
--j;
}
}
Я ищу решение O (n).
Хитрость заключается в том, чтобы понять, что нам нужно всего лишь найти минимум j такой, что (A[0] + ... + A[j-1]) == (A[0] + ... + A[i]) - 1. A[j] + ... + A[i] совпадает с (A[0] + ... + A[i]) - (A[0] + ... + A[j-1]), поэтому, как только мы найдем правильный j, сумма между j и я будет равна 1.
Любое раннее j не дало бы положительного значения, и любой последующий j не дал бы нам максимально возможной последовательности. Если мы будем отслеживать, где мы сначала достигаем каждого последующего отрицательного значения, то мы можем легко найти правильный j для любого заданного i.
Вот реализация С++:
vector<int> solve(const vector<int> &A)
{
int n = A.size();
int sum = 0;
int min = 0;
vector<int> low_points;
low_points.push_back(-1);
// low_points[0] is the position where we first reached a sum of 0
// which is just before the first index.
vector<int> B(n,-1);
for (int i=0; i!=n; ++i) {
sum += A[i];
if (sum<min) {
min = sum;
low_points.push_back(i);
// low_points[-sum] will be the index where the sum was first
// reached.
}
else if (sum>min) {
// Go back to where the sum was one less than what it is now,
// or go all the way back to the beginning if the sum is
// positive.
int index = sum<1 ? -(sum-1) : 0;
int length = i-low_points[index];
if (length>1) {
B[i] = length;
}
}
}
return B;
}
Вы можете рассмотреть сумму + 1/-1, как на моем графике. Мы начинаем с 0 (это не имеет значения).
Итак: вы хотите, при рассмотрении любой точки, получить слева другую точку, которая наиболее далеко и ниже.
1 построить и сохранить сумму
Требуется n итераций: O (n)
2 постройте значение table = > point, итерацию каждой точки и сохранение самого слева:
Вы получаете: 0 = > a, 1 = > b (не d), 2 = > c (не e, i, k), 3 = > f (не h), 4 = > g (не m), 5 = > n, 6 = > o
Требуется n итераций: O (n)
3 на каждом уровне (скажем 0, 1, 2, 3,...) = > вы держите точку далеко, что ниже:
уровень 0 = > a
уровень 1 = > a
и т.д.. = > он всегда будет.
Предположим, что граф начинается в точке g:
4 = > g
3 = > h
2 = > i
5 = > g
6 = > g
Тогда: если точка чуть выше 3 (тогда 4: as m) = > , она будет h
Требуется также n операций с max (высота графика точно).
4 итерации каждой точки: ваш B [i].
В каждой точке, скажем, h: sum = 3, вы берете ее намного ниже (таблица работы 3): в моей схеме всегда a = 0;
Предположим, что граф начинается в точке g:
для точек
g, h, i, k = > ничего
j = > i
l = > i
m = > h
n = > g
Вы можете комбинировать некоторые операции в одной итерации.