XOR-sum.py

from functools import reduce

def naive(ar, length):
    # Наивное решение полным перебором. Сложность - O(n**2).
    # Проверяем все возможные подмассивы в массиве.
    # Уверен, что не пройдет по быстродействию.
    if 0 == length:
        return 0
    if 1 == length:
        return 1 if ar[0] else 0
    result = 0
    for i in range(length - 1):
        s = ar[i]
        for j in range(i + 1, length):
            s = s ^ ar[j]
            if s:
                result = max(result, j - i + 1)
    return result

def task(ar, length):
    # Если последовательность пуста, ответ - 0
    if 0 == length:
        return 0
    # Если массив состоит из одних нулей, ответ - 0
    if all(elem == 0 for elem in ar):
        return 0
    # Если xor-сумма всего массива ненулевая, ответ - весь массив
    if 0 != reduce(lambda x,y: x^y, ar, 0):
        return length
    # Иначе ищем первый и последний ненулевые элементы
    first = 0
    for i in range(length):
        if ar[i]:
            first = i
            break
    last = length - 1
    for i in range(length - 1, -1, -1):
        if ar[i]:
            last = i
            break
    # Возвращаем длину подмассива, отрезав часть с той стороны, с которой меньше нулей
    return length - min(first, length - last - 1) - 1


# Набор тестов
ar = []
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [1]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [0, 0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [0, 1]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [1, 0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [0, 0, 0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [0, 1, 0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [1, 0, 1]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [0, 0, 3, 7, 4, 0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [1, 0, 0, 3, 7, 4, 0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [1, 0, 0, 3, 7, 4, 0, 1]
assert(naive(ar, len(ar)) == task(ar, len(ar)))

ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]
assert(naive(ar, len(ar)) == task(ar, len(ar)))