чтобы программа находила ту симметрию, в котором симметрия начинается с большего числа

Question

Код в самом внизу.

Программа ищет симметрию и выводит индекс начального числа симметрии и его длину. Дело в том, что нужно, если в списке чисел несколько симметрии, она считала ту симметрию, в котором симметрия начинается с наибольшего числа среди этих симметрии. Например, вот

Ввод:

-15 19 16 8 15 10 -14 -15 17 -17 -7 -13 -11 4 1 16 -9 13 6 13 -17 -19 9 11 5 -19 3 -20 3 16 -18 11 8 6 14 15 14 -1

Вывод:

34 3

Тут симметрии несколько, одна симметрия начинается с числа под индексом 17 и длина этой симметрии 3, но из-за того, что у второй симметрии(симметрия начинается с числа под индексом 34) начальное число больше, выводит его

Вот сам код:

data = list(map(int, input().split()))

pos_min = 0
size_max = 0

for pos in range(len(data)):
    for size in range(2, len(data) - pos + 1):
        if data[pos:pos+size] == list(reversed(data[pos:pos+size])) and size > size_max:
            size_max = size
            pos_min = pos

if size_max == 0:
    print(data.index(max(data)), 1)
else:
    print(pos_min, size_max)

Answer 1

Вариант №1

Хранить все симметричные последовательности в списке с их размерами, первыми элементами и позициями. Потом список отсортировать и вывести максимальные элемент.

#data = list(map(int, input().split()))
data = list(map(int, "-15 19 16 8 15 10 -14 -15 17 -17 -7 -13 -11 4 1 16 -9 13 6 13 -17 -19 9 11 5 -19 3 -20 3 16 -18 11 8 6 14 15 14 -1".split()))

symmetric = []
for pos in range(len(data)):
    for size in range(2, len(data) - pos + 1):
        if data[pos:pos+size] == list(reversed(data[pos:pos+size])):
            symmetric.append((size, data[pos], pos))

if symmetric:
    symmetric.sort()
    print(symmetric[-1][2], symmetric[-1][0])
else:
    print(data.index(max(data)), 1)

Вариант №2

Хранить длину максимальной последовательности и её позицию, но обновлять их только если:

новая последовательность длиннее; или
она по длине такая же, но её первый член больше, чем у предыдущей найденной последовательности такой же длины

#data = list(map(int, input().split()))
data = list(map(int, "-15 19 16 8 15 10 -14 -15 17 -17 -7 -13 -11 4 1 16 -9 13 6 13 -17 -19 9 11 5 -19 3 -20 3 16 -18 11 8 6 14 15 14 -1".split()))

size_max = 0
pos_max  = 0
for pos in range(len(data)):
    for size in range(2, len(data) - pos + 1):
        if data[pos:pos+size] == list(reversed(data[pos:pos+size])):
            if (size > size_max) or (size == size_max and data[pos] > data[pos_max]):
                size_max = size
                pos_max = pos

if size_max:
    print(pos_max, size_max)
else:
    print(data.index(max(data)), 1)

Вариант №3 (оптимизированный)

Похож на вариант №2. Только сразу ищем последовательности в порядке уменьшения их длины. Что позволяет избежать лишнего сканирования последовательности на наличие более коротких симметрий если уже найдена более длинная.

#data = list(map(int, input().split()))
data = list(map(int, "-15 19 16 8 15 10 -14 -15 17 -17 -7 -13 -11 4 1 16 -9 13 6 13 -17 -19 9 11 5 -19 3 -20 3 16 -18 11 8 6 14 15 14 -1".split()))

pos_max = None
for size in range(len(data), 0, -1):
    for pos in range(0, len(data) - size + 1):
        if data[pos:pos+size] == list(reversed(data[pos:pos+size])):
            if pos_max is None or data[pos] > data[pos_max]:
                pos_max = pos

    if pos_max is not None:
        break

print(pos_max, size)

БЛОГ НА HUSL

чтобы программа находила ту симметрию, в котором симметрия начинается с большего числа

Ответы (1 шт):

Вариант №1

Вариант №2

Вариант №3 (оптимизированный)