У нас есть бит-массив, как показано ниже
{1 0 1 0 0 1 0 1}
Число бит в указанном массиве равно 8
Если мы возьмем диапазон от [1,5]
, тогда число бит в диапазоне [1,5]
равно [0 1 0 0 1]
.
Если мы перевернем этот диапазон, то после листания будет [ 1 0 1 1 0]
Таким образом, общее число 1 после перевернутого диапазона [1,5]
составляет [1 1 0 1 1 0 0 1] = 5
Если мы возьмем диапазон от [1,6]
, тогда число бит в диапазоне [1,6] будет [0 1 0 0 1 0]
.
Если мы перевернем этот диапазон, то после листания будет [ 1 0 1 1 0 1]
Таким образом, общее число 1 после листания [1,5] диапазона составляет [1 1 0 1 1 0 1 1] = 6
Итак, ответ - диапазон [1,6]
, и после листания мы можем получить 6 1 в массиве
Есть ли хороший алгоритм, который может решить эту проблему. Я думаю только о динамическом программировании, потому что эта проблема может быть разбита на подвыборы, которые можно объединить.