Сложность: medium
Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь.
Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию.
Пример:
Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.
👨💻 Алгоритм:
1️⃣Обработка базовых случаев:
Если массив nums пуст, возвращаем 0. Если в массиве nums только один дом, возвращаем значение этого дома.
2️⃣Разделение задачи на две подзадачи:
Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию rob_simple с параметрами 0 и len(nums) - 2. Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и len(nums) - 1.
3️⃣Сравнение результатов и возврат максимального значения:
Возвращаем максимальное значение из двух полученных результатов.
😎 Решение:
class Solution:
def rob(self, nums):
if not nums:
return 0
if len(nums) == 1:
return nums[0]
max1 = self.rob_simple(nums, 0, len(nums) - 2)
max2 = self.rob_simple(nums, 1, len(nums) - 1)
return max(max1, max2)
def rob_simple(self, nums, start, end):
t1, t2 = 0, 0
for i in range(start, end + 1):
temp = t1
current = nums[i]
t1 = max(current + t2, t1)
t2 = temp
return t1
Ставь 👍 и забирай 📚 Базу знаний