Сложность: 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 и nums.count - 2.
Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и nums.count - 1.
3⃣Сравнение результатов и возврат максимального значения:
Возвращаем максимальное значение из двух полученных результатов.
😎 Решение:
class Solution {
func rob(_ nums: [Int]) -> Int {
if nums.isEmpty { return 0 }
if nums.count == 1 { return nums[0] }
let max1 = rob_simple(nums, 0, nums.count - 2)
let max2 = rob_simple(nums, 1, nums.count - 1)
return max(max1, max2)
}
func rob_simple(_ nums: [Int], _ start: Int, _ end: Int) -> Int {
var t1 = 0
var t2 = 0
for i in start...end {
let temp = t1
let current = nums[i]
t1 = max(current + t2, t1)
t2 = temp
}
return t1
}
}Ставь 👍 и забирай 📚 Базу знаний