Поиск подмассива в массиве

[frankenstein]

Дан массив длины n из нулей и единиц. Найти в нем подмассив макс. длины, в котором
количество единиц равно количеству нулей. Ограничение по времени и памяти O(n)
Вроде задача, простая, но я смог бы реализовать только перебор, как решить за O(n),
не знаю. Нужна ваша помощь.
Ведь, фактически, задача сводится к тому, чтобы найти два числа i и j, таких что
$ |i-j|+1 $ должно быть четным числом и
$ a[i] + a[i+1] + ... + a[j] = (|i-j|+1)/2 $

[iifat]

На псевдоалголе, что ли, попробовать.

int s := 0, beg := 0, fin := 0, len := 0;
int b [0:n]; b [0] = 1; for i from 1 to n do b [i] := 0 od;
for i from 1 to n do
  S +:= (a [i] = 1|1|-1);
  if b [s] = 0 then b [s] := i elseif len < i - b [s] + 1 then beg := b [s]; fin := i; len := i - b [s] + 1 fi;
od

Заводим рабочий массив, где в i-й ячейке — самый ранний индекс, такой что сумма от 1 до него равна i. Надо найти самый длинный отрезок, не меняющий эту сумму.

[Null]

Можно так: Пусть $b[i]] $- разность между количеством 0 и 1 среди первых $i$ чисел. Надо найти $\max\limits_{\substack{0\le k<l \le n\\b[l]=b[k]}} |l-k|$. Это можно сделать за $n\log n$

[iifat]

А мой способ, по-моему, линейный, вам чем-то не пнравился?

[Null]

$s$ может быть отрицательным или 0(или я вас не так понял и вы считаете только количество 1). А так да $O(n)$, я усложнил

[nikvic]

iifat в сообщении #796969 писал(а):

Заводим рабочий массив, где в i-й ячейке — самый ранний индекс, такой что сумма от 1 до него равна i.

Удобнее вместо числа единиц - разность числа единиц и нулей, так что рабочий массив сам индексируется целыми числами.

Но нужна пара индексов. Первый - самый ранний, второй - самый поздний - для текущего положения просмотра.

[Null]

Цитата:

второй - самый поздний - для текущего положения просмотра.

Мы и так знаем текущее положение просмотра

[nikvic]

Null в сообщении #798108 писал(а):

Мы и так знаем текущее положение просмотра

И используем его для возможного увеличения второго члена пары, занумерованной текущим значением разности.

Если ещё помнить текущий рекорд, то алгоритм на каждом шаге просмотра "выдаёт" результат.

[iifat]

Null в сообщении #798095 писал(а):

$s$ может быть отрицательным или 0

0 я учёл, а отрицательные и правда забыл.Спасибо.

int s := 0, beg := 0, fin := 0, len := 0;
int b [-n:n]; for i from -n to n do b [i] := 0 od; b [0] = 1;
for i from 1 to n do
   S +:= (a [i] = 1|1|-1);
   if b [s] = 0 then b [s] := i elseif len < i - b [s] + 1 then beg := b [s]; fin := i; len := i - b [s] + 1 fi;
od

[svv]

Неужели кто-то еще знает и помнит непревзойденный и несравненный Algol 68!

[nikvic]

svv в сообщении #808231 писал(а):

Неужели кто-то еще знает и помнит непревзойденный и несравненный Algol 68!

Остался текст -
"""Алголом жечь сердца людей!

[iifat]

Первая любовь — она бессмертна

[svv]

Да!