Максимальная сумма подпоследовательности без соседей (вариант с кольцом)
Hard
Дан массив домов по кругу: первый и последний элементы считаются соседями. Нужно выбрать подмножество домов с максимальной суммой денег так, чтобы никакие два выбранных дома не стояли рядом (включая пару «первый–последний»). Верните эту максимальную сумму.
Примеры:
Вход:
[2, 3, 2]
Выход:
3
Объяснение: [2,3,2]: первый и последний оба равны 2 и являются соседями по кругу, оба взять нельзя. Лучший выбор — одно число 3.
Вход:
[1, 2, 3, 1]
Выход:
4
Объяснение: [1,2,3,1]: можно взять 1 (первый) и 3, сумма 4; либо 2 и 1 (последний), тоже 4. Больше набрать нельзя.
Вход:
[5, 5, 10, 100, 10, 5]
Выход:
110
Объяснение: [5,5,10,100,10,5]: индексы 0 и 5 соседи. Оптимум: 5 (индекс 1) + 100 (индекс 3) + 5 (индекс 5) = 110; эти три дома попарно не соседние.
Ограничения:
1 <= n <= 10^5; элементы целые (могут быть отрицательные)
Комментарии (0)
Войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!