algorithm - 相同长度的最长连续子列表的长度，以及子列表元素求和的奇偶性

Question

给定两个列表，例如:

a = {0, 1, 0, 1, 0, 1} - 6 个元素

b = {1, 1, 1, 0} - 4 个元素

我需要找到:最长的连续子列表的长度(由其中一个列表的一个连续片段组成) 具有相同的长度和子列表的求和元素的奇偶校验。

对于这个例子，答案是 3(“a”列表中的第 3、4、5 个元素和“b”列表中的前 3 个元素)。

列表按固定顺序排列。列表中的值是大于或等于 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，分布如下:

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

请注意，我们可以利用赔率之间连续 block 的任意组合，并根据我们是否包含或排除左或右奇数元素中的一个来设置其奇偶校验。例如:

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