Длина самых длинных смежных подсписков одинаковой длины и четность суммируемых элементов подсписка

Question

Имеется два списка, например:

a = {0, 1, 0, 1, 0 , 1} - 6 элементов

b = { 1, 1, 1 , 0} - 4 элемента

Мне нужно найти: длину самых длинных непрерывных подсписков (составленных из одного непрерывного фрагмента одного из списков) такой же длины и четности суммируемых элементов подсписка.

Для этого примера ответом является 3 (3-й, 4-й, 5-й элемент из списка «a» и 3 первых элемента из списка «b»).

Списки в фиксированном порядке. Значения в списке являются целыми числами, большими или равными 0.

Я застрял со сложностью около O (n ^ 2) в худшем случае. Вот как я решил проблему.

  Starting with the length of the longest possible sublist (in example it is 4)
while (length > 0){
(here I use "for" loop) Finding possible parities of that length or till for at least one of the lists all parities, within some of possible sublists, are found (0 and 1)
If there are in both lists, sublists of the same parity then it is the answer; break; if not: length--; }
if there hasn't been found any answer then the answer is 0

Очевидно, что есть более эффективный способ решения этой проблемы, но я не мог придумать ни одного, ни найти что-то, что могло бы мне помочь.

У вас есть идеи? Может быть, у кого-то здесь была похожая проблема, но я не смог ее найти? Если есть что-то, что вам нужно уточнить, дайте мне знать.

Если проблема нуждается в разъяснении, а не в голосовании, попросите разъяснения. Спасибо.

РЕДАКТИРОВАТЬ: Вот еще несколько примеров:

a = { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } - 10 элементов

b = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } - 10 элементов

Ответ: 10

a = { 0, 0, 0, 0, 0, 0, 0 } - 7 элементов

b = { 0, 0, 0, 0, 0, 0, 0 , 0} - 8 элементов

Ответ: 7

a = { 0, 0, 0 , 1, 0, 0, 0} - 7 элементов

b = { 0, 0, 0 , 0, 0, 0, 0, 0, 0, 0} - 10 элементов

Ответ: 3

a = {0, 1, 0, 0, 1, 1, 1 } - 7 элементов

b = { 1, 1, 1, 0, 1, 0 } - 6 элементов

Ответ: 6

Answer 1

Приведенные вами примеры допускают тривиальные O(n) решения, используя метод ниже.Не могли бы вы (или кто-то другой) привести хотя бы один пример, который заставил бы этот метод быть неэффективным?(Таким образом, возможно, помогая нам улучшить его:)

Мне кажется, как показано в моем другом частичном ответе, что чем больше разнообразия или случайности вы пытаетесь внести во входные данные, тем больше вероятность того, что оптимальныйсовпадение может быть найдено быстро из-за недостатка или регулярности в недоступных длинах.

Метод:

Мы можем вычислить в O(n) времени и пространстве список частот для нечетных вхождений и их индексов(они определяют переключатели четности).Начиная с каждого конца полного диапазона, мы можем рекурсивно свернуть ту или иную сторону, чтобы определить возможный диапазон, перейдя к следующему вхождению в этом предварительно рассчитанном списке.(Для любой фиксированной стороны мы также можем выполнить бинарный поиск диапазона, разделив пополам другую сторону.)

Например:

b = [1,   1,   1,   0]
l: (0,1)(1,2)(2,3)

Odd length 3-4, indexes: 0-(2..3)
Even length (collapse left):
  2-3, indexes: 1-(2..3)


a = [0, 1, 0, 1, 0, 1]
l:    (1,1) (3,2) (5,3)

Odd length 5-6, indexes: (0..1)-5
Even length (collapse right or left):
  3-5, indexes: (0..1)-(3..4)

Next odd length (collapse right or left again):
  1-3, indexes: (0..1)-(1..2)

Так как у нас нет соответствия для длины 4,следующий лучший результат - 3.

a = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Тривиальный, полный диапазон совпадений.

a = [0, 0, 0, 0, 0, 0, 0]
b = [0, 0, 0, 0, 0, 0, 0, 0]

Тривиальный, без лишних длин.

a = [0, 0, 0, 1, 0, 0, 0]
b = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Тривиальный, только один выборчетной длины, свернуть вправо или влево для диапазонов 1-3.

a = [0, 1, 0, 0, 1, 1, 1]
b = [1, 1, 1, 0, 1, 0]

Тривиально, не требуется сложение, полный четный диапазон сразу совпадает, a indexes: (0..1)-6, b indexes: 0-(4..5)

Answer 2

Вот частичный ответ и направление для рассмотрения.Скажем, расстояния, означающие количество четных чисел между нечетными числами o, были распределены так:

| o <- 2 -> o <- 4 -> o <- 5 -> o <- 17 -> |

Обратите внимание, что мы можем использовать любую комбинацию смежных блоков между коэффициентами и установить их четностьосновано на том, если мы включим или исключим только один из левого или правого нечетного элемента.Например:

4 + 1 + 5 (±2) odd:
     o <- 4 -> o <- 5 -> o
  or
    [exclude] <- 4 -> o <- 5 -> [exclude]

4 + 1 + 5 (+1) even:
     [exclude] <- 4 -> o <- 5 -> o
  or
     o <- 4 -> o <- 5 -> [exclude]

Но если мы исключим нечетное на одном или обоих концах, мы можем использовать диапазон, расширяющийся до следующего нечетного:

[4..0] + 1 + 5 (+1) even:
  [exclude] <- 4 -> o <- 5 -> o

(+1) 4 + 1 + [0..5] even:
  o <- 4 -> o <- 5 -> [exclude]

Так что на самом деле,может быть более полезным посмотреть, какую длину последовательности мы не можем достичь, поскольку их число намного меньше или может быть быстро ранжировано.Давайте рассмотрим некоторые из ваших примеров:

{0, 1, 0, 1, 0, 1}
Odd-sum lengths we cannot reach: 4
Even-sum lengths we cannot reach: 2, 6

{1, 1, 1, 0}
Odd-sum lengths we cannot reach: None
Even-sum lengths we cannot reach: 4


{0, 1, 0, 0, 1, 1, 1}
Unreachable even-sum lengths: None
Unreachable odd-sum lengths: 7

{1, 1, 1, 0, 1, 0}
Unreachable even-sum lengths: None
Unreachable odd-sum lengths: 6


{0, 0, 0, 1, 0, 0, 0}
Unreachable even-sum lengths: > 3
Unreachable odd-sum lengths: None

{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
Unreachable even-sum lengths: None
Unreachable odd-sum lengths: All