我试图从黑客级别解决这个问题我尝试了暴力破解解决方案，但它似乎没有工作。有人可以有一个想法来有效地解决这个问题。 https://www.hackerrank.com/contests/sep13/challenges/sherlock-puzzle最长的连续子序列，使零的数目的两倍小于等于三倍的数目
鉴于它包含一个二进制串（S）“0'和” 1'和整数K， 找到的（S * K）的最长连续子序列的长度（L），使得零的数量的两倍是< =该序列中的数目（2 *＃0s= 3 *＃1s）的三倍。
S * K定义如下：S * 1 = S S * K = S + S *（K - 1）
输入格式 第一个（只）行包含一个整数K和二进制字符串S由一个空格分隔。
约束 = | S | < = 1,000,000 = K < = 1,000,000
输出格式 一个整数L - 答案的测试用例
这里有一个提示：
让我们首先假设K = 1和该S看起来像（使用点为0）：
..1...11...11.....111111....111....
e f b a c d
的关键是要注意，如果最长的接受序列包含1它会也包含任何相邻的。例如，如果最长的序列包含在a处的1，则它也将包含在b和c（含）之间的所有值。
所以你只需要分析那些块的顺序。
主要问题是：如果你从某个块开始，你可以把它放到下一块块吗？例如，如果您从e开始，则可以将其设置为f而不是b。如果你开始在b你可以在d等使其向块
然后概括分析K> 1
这是一个好的开始，但不幸的是不够。你也可以压缩像'1 * n 0 * k 1 * m'这样的块，其中'3 * min（m，n）> = 2 * k'。显然这些街区总是在一起。通过从一个块到另一个块从另一个块到另一个从左到右找出最长的序列例如在该序列上失败：“1100100010011”，其中解决方案是整个序列。 – jakab922
蛮力显然是行不通的，因为它是O((n * k) ** 2)。我将在这个答案中使用python样式列表解析。你需要一个数组t = [3 if el == "1" else - 2 for el in S]。现在如果您使用p[i] = t[0] + ... + t[i]数组，您可以看到在k == 1的情况下，您基本上在寻找一对（i，j），这样p[j] - (p[i - 1] if i != 0 else 0) >= 0为真，j - i为 这些对中的最大值。现在对于每个i in 0..n-1，你必须找到它是j对，这样以上是最大的。这可以在O(log n)针对特定的i完成，所以这给出了和k1 = 1情况下的O(n log n)解决方案。这可以扩展到一般情况下的O(n log n)解决方案（有一个技巧可以找到可以覆盖的最大块）。此外，还有一个解决此问题的O(n)，但您需要进一步检查p序列。尽管如此，我并不建议用脚本语言编写解决方案。即使O(n)解决方案超时蟒蛇...
请显示您的“蛮力解决方案”，否则它看起来我们正在为你做所有的工作。 – chux
嗨。我不在寻找代码。我所需要的只是解决这个问题的想法。网站上有数百种解决方案。 – user2615516
看起来像一个动态的编程问题 –