LeetCode № 198. Грабитель дома

Я уверен, что есть лучшие способы решить эту проблему, но этот блог расскажет вам, как я подошел к этой проблеме. Вот задача, указанная на сайте LeetCode:

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

Имея список неотрицательных целых чисел, представляющих сумму денег в каждом доме, определите максимальную сумму денег, которую вы можете ограбить сегодня вечером, не поставив в известность полицию.

Пример 1:

Input: [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.

Пример 2:

Input: [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
             Total amount you can rob = 2 + 9 + 1 = 12.

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

var rob = function(nums) {
  let even = [];
  let odd = [];
  
  nums.map((e,i) => {
    if (i % 2 === 0) {
      even.push(e);
    } else {
      odd.push(e)
    }
  });
  let e = even.reduce((a,b) => a + b);
  let o = odd.reduce((a,b) => a + b);
  return e > o ? e : o;
};

Я сопоставляю массив nums и использую условное выражение с i % 2 === 0, чтобы определить, имеет ли элемент четный или нечетный индекс. Если он четный, он поместит элемент в четный массив, а если нечетный - в нечетный массив.

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

Наконец, я пишу тройку, чтобы вернуть большую сумму.