在长度为n的二进制循环数组中，找出它是否可以被划分，使得大小为m的大多数相邻元素组的1比0多

Question

例如，如果数组为001101100，则存在一个分区011011000，其中最大组的1比0多。然而，在100110100中却没有。我尝试过暴力破解方法，它需要O(n^3)时间。请建议一种更有效的方法，因为这不起作用。

Answer 1

有一个重用组和的O(n)-time算法。我假设“大多数”意味着多数而不是最大化，但改变并不难。

def circular(array, m):
    n = len(array)
    assert n % 2 == 1
    assert m % 2 == 1
    assert n % m == 0
    groupsums = [sum(array[j * m:(j + 1) * m]) for j in range(n // m)]
    for i in range(m):
        if sum(groupsum > m // 2 for groupsum in groupsums) > (n // m) // 2:
            return [[array[(j * m + k) % n] for k in range(i, i + m)]
                    for j in range(n // m)]
        for j in range(n // m):
            groupsums[j] -= array[(j * m + i) % n]
            groupsums[j] += array[((j + 1) * m + i) % n]


print(circular([0, 0, 1, 1, 0, 1, 1, 0, 0], 3))
print(circular([1, 0, 0, 1, 1, 0, 1, 0, 0], 3))
print(circular([0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1], 3))