长度相同的最长连续子列表的长度和子列表中之和元素的奇偶校验

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，0} - 10元素

答: 10

A= {0，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 -> |

请注意，如果只包含或排除左或右奇数元素中的一个，则可以利用概率之间的任何连续块组合，并根据其奇偶性设置奇偶。例如：

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

Answer 2

您提供的示例允许使用下面的方法提供一些简单的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)