Задача: 213. House Robber II
Сложность: 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 и count($nums) - 2.
Находим максимальную сумму для подмассива домов от второго до последнего, вызывая функцию rob_simple с параметрами 1 и count($nums) - 1.

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

😎 Решение:

class Solution {
    public function rob($nums) {
        if (count($nums) == 0) return 0;
        if (count($nums) == 1) return $nums[0];

        $max1 = $this->rob_simple($nums, 0, count($nums) - 2);
        $max2 = $this->rob_simple($nums, 1, count($nums) - 1);

        return max($max1, $max2);
    }

    private function rob_simple($nums, $start, $end) {
        $t1 = 0;
        $t2 = 0;

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

        return $t1;
    }
}

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