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

标签： algorithmperformanceoptimization

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)