← К задачам Режим собеседования 30:00
Обычный режим ← Предыдущая Следующая →

4123. Максимальная сумма подпоследовательности без соседей (вариант с кольцом)

Medium 2 решили
Дан массив чисел nums — «дома» стоят по кругу: первый и последний элементы тоже соседи.

Выберите подмножество домов с максимальной суммой так, чтобы никакие два выбранных дома не стояли рядом (включая пару «первый–последний»).

Можно не брать никого → сумма 0 (это важно, если все числа отрицательные).
Один дом сам себе не сосед: для [5] ответ 5, для [-3] выгоднее 0.

Примеры:

Вход: [2, 3, 2]
Выход: 3
Объяснение: Крайние 2 соседи по кругу — оба брать нельзя. Лучше одно число 3.
Вход: [1, 2, 3, 1]
Выход: 4
Объяснение: 1+3 = 4 или 2+1 = 4.
Вход: [-1, -2, -3]
Выход: 0
Объяснение: Все отрицательные — выгоднее ничего не брать → 0.

Ограничения:

1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4

Теги:

Массивы Динамическое программирование

Комментарии (0)

Зарегистрируйтесь или войдите, чтобы оставить комментарий

Пока нет комментариев. Будьте первым!