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
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!