4106. Сумма неподряд идущих элементов
Easy
3 решили
Дан массив
Можно не брать ни одного элемента: тогда сумма равна
nums. Верните максимальную сумму подмножества (не обязательно непрерывного), в котором никакие два выбранных элемента не стоят на соседних позициях.Можно не брать ни одного элемента: тогда сумма равна
0. Это важно при отрицательных числах: для [-1,-2,-3] ответ 0, а не -1.Примеры:
Вход:
[2, 7, 9, 3, 1]
Выход:
12
Объяснение: 2+9+1 = 12 (индексы 0, 2, 4); 7+3=10 меньше.
Вход:
[1, 2, 3, 1]
Выход:
4
Объяснение: 1+3 или 2+1 — максимум 4.
Вход:
[5]
Выход:
5
Объяснение: Один положительный элемент выгоднее пустого подмножества.
Вход:
[-1, -2, -3]
Выход:
0
Объяснение: Все отрицательные: выгоднее не брать ничего → 0, а не -1.
Ограничения:
1 <= n <= 10^5; -10^6 <= nums[i] <= 10^6
Решите эту задачу в браузере
Создайте бесплатный аккаунт — редактор Python, Java, JavaScript и Go, проверка на тестах за секунды.
Комментарии (0)
Зарегистрируйтесь или войдите, чтобы оставить комментарий
Пока нет комментариев. Будьте первым!