Блог

Я пытаюсь решить эту проблему в TopCoder, которая заключается в следующем. У меня есть своя реализация, но я не знаю, где я ошибаюсь. Спасибо

Старая песня гласит: «Иди вперед и ненавидь своего соседа», и жители Онетинвилля приняли эти слова близко к сердцу. Каждый житель ненавидит своих ближайших соседей с обеих сторон. Никто не хочет жить дальше от городского колодца, чем его соседи, поэтому город был устроен большим кольцом вокруг колодца. К сожалению, городской колодец находится в аварийном состоянии и нуждается в восстановлении. Вас наняли для сбора пожертвований в фонд Save Our Well.

Каждый из жителей города готов пожертвовать определенную сумму, указанную в пожертвованиях, которые перечислены в порядке по часовой стрелке вокруг колодца. Однако никто не хочет вносить вклад в фонд, в который также внес свой вклад его сосед. Соседние соседи всегда перечислены последовательно в пожертвованиях, за исключением того, что первая и последняя записи в пожертвованиях также относятся к соседям по соседству. Вы должны рассчитать и вернуть максимальную сумму пожертвований, которую можно собрать.

Это моя реализация, но я получаю сообщение о неправильном ответе от судьи.

 def badNeighbors(donation:[int]) -> int:
    globalmax = 0
    if len(donation) == 0:
        return 0
    table = [[0,0] for _ in range(len(donation))]
    table[0][1] = 1
    for i in range(len(donation)):
        table[i][0] = donation[i]
        for j in range(i):
            if j != i-1:
                if table[i][0] < donation[i]   table[j][0]:
                    table[i][0] = donation[i]   table[j][0]

                    if table[j][1] == 1:
                        table[i][1] = 1 
                    else:
                        table[i][1] = 0
#     print(table)
    if table[-1][1] == 1:
        table[-1][0] = table[-1][0] - table[0][0]
    return max(table)[0]
 

Примеры тестовых примеров, которые я могу пройти:
Тест #1

 { 10, 3, 2, 5, 7, 8 }
 

19

Максимальное пожертвование составляет 19, достигается 10 2 7 . Было бы лучше взять 10 5 8 за исключением того, что пожертвования в размере 10 и 8 поступили от соседей.

Тест #2

 { 11, 15 }
 

15

Тест #3

 { 7, 7, 7, 7, 7, 7, 7 }
 

21

Тест #4

 { 1, 2, 3, 4, 5, 1, 2, 3, 4, 5 }
 

16

Тест #5

 { 94, 40, 49, 65, 21, 21, 106, 80, 92, 81, 679, 4, 61, 6, 237, 12, 72, 74, 29, 95, 265, 35, 47, 1, 61, 397, 52, 72, 37, 51, 1, 81, 45, 435, 7, 36, 57, 86, 81, 72 }
 

2926