Решение задачи про поиск наибольшего подмассива из 0 и 1, где сумма их кол-ва равна друг другу

info@vsetut.pro

Стать автором

Вернуться

10.01.2025 05:16:14 | Хабр

Хабы: Алгоритмы

Попалась мне одна интересная задача ,суть которой - найти наибольший отрезок в массиве единиц и нулей ,где суммы их кол-ва равны друг другу. Например ,имеем массив [0, 1, 0, 1, 0]. Длина наибольшего подмассива ,где кол-во нулей равно кол-ву единиц = 4. Под этот критерий подходит подмассив [{0, 1, 0, 1}, 0] ,а так же [0, {1, 0, 1, 0}]. В обоих случаях сумма всех нулей = 2 ,а сумма всех единиц равна тоже 2. Длина такой последовательности = 4 ,и это должно быть ответом.

Сперва можно немного поработать над данными ,чтобы в будущем можно было проще вычислять такие отрезки ,где суммы 1 и 0 равны друг другу. Например ,для отрезка [0, 1, 0, 1] общая сумма значений равна 2 (0 + 1 + 0 + 1). Можно сделать вывод ,что сумма 1 и 0 равна в этом отрезке ,если сумма значений равна половине длины подмассива. Для нашего случая получается ,что (0 + 1 + 0 + 1) = 2 = 4/2 (половина длины подмассива). Но гораздо проще было бы проводить расчеты ,если бы необходимая сумма значений была бы константой ,например 0. В таком случае мы можем заменить все нули на -1 ,и таким образом получим [-1, 1, -1, 1] ,где сумма таких элементов будет равна 0.

На JavaScript это можно сделать следующим образом: arr.map(x => x || -1).

Далее нам потребуется цикл по длине arr:

Подробнее