Задача: 213. House Robber II
Сложность: medium

Вы профессиональный грабитель, планирующий ограбить дома вдоль улицы. В каждом доме спрятано определенное количество денег. Все дома в этом месте расположены по кругу, что означает, что первый дом является соседом последнего. Между тем, в соседних домах установлена охранная система, которая автоматически свяжется с полицией, если два соседних дома будут взломаны в одну ночь.
Дан массив целых чисел nums, представляющий количество денег в каждом доме, верните максимальную сумму денег, которую вы можете ограбить этой ночью, не вызвав полицию.

Пример 1:

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️⃣ Разделение задачи на две подзадачи:
Находим максимальную сумму для подмассива домов от первого до предпоследнего, вызывая функцию robSimple с параметрами 0 и nums.length - 2.
Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию robSimple с параметрами 1 и nums.length - 1.

3️⃣ Сравнение результатов и возврат максимального значения:
Вернуть максимальное значение из двух полученных результатов.

😎 Решение:

class Solution {
    rob(nums) {
        if (nums.length === 0) return 0;
        if (nums.length === 1) return nums[0];

        let max1 = this.robSimple(nums, 0, nums.length - 2);
        let max2 = this.robSimple(nums, 1, nums.length - 1);

        return Math.max(max1, max2);
    }

    robSimple(nums, start, end) {
        let t1 = 0;
        let t2 = 0;

        for (let i = start; i <= end; i++) {
            let temp = t1;
            let current = nums[i];
            t1 = Math.max(current + t2, t1);
            t2 = temp;
        }

        return t1;
    }
}

Ставь 👍 и забирай 📚 Базу знаний