Проблема

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

Концепция

Несколько вещей, которые следует помнить о проблеме:

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

Давайте рассмотрим пример с изображенным здесь массивом.

Лучше всего решить эту проблему с помощью динамического программирования. Но что это? Согласно Википедии:

Динамическое программирование - это одновременно метод математической оптимизации и метод компьютерного программирования. Метод был разработан Ричардом Беллманом в 1950-х годах и нашел применение во многих областях, от аэрокосмической техники до экономики.

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

Если подзадачи могут быть рекурсивно вложены внутрь более крупных задач, так что применимы методы динамического программирования, тогда существует связь между значением более крупной проблемы и значениями подзадач. [1] В литературе по оптимизации это соотношение называется уравнением Беллмана.

Важным моментом здесь является то, что мы просто находим решение, разбивая большую проблему на более мелкие, чтобы решить большую проблему! Вот и все!

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

Индекс 0: единственный вариант на этом этапе - это значение самого индекса 0, поэтому мы сохраняем 7 во вспомогательном массиве.

Индекс 1: Затем мы смотрим на 10, и максимальная сумма в этой точке равна максимальному значению 7 и 10. Мы не можем сложить их вместе, потому что они находятся рядом друг с другом.

Индекс 2: на этом этапе мы можем сложить 7 и 12 вместе, потому что они не находятся рядом друг с другом, поэтому максимальная сумма равна 19.

Индекс 3: Теперь у нас есть несколько вариантов!

  • 7+12 = 19
  • 10+7 = 17
  • 7+7 = 14

Очевидно, 19 - это максимальная сумма, поэтому мы сохраним 19 во вспомогательном массиве. Здесь проиллюстрирован важный момент: нам не обязательно использовать значение в индексе, в котором мы сейчас находимся.

Индекс 4: По мере роста входного массива количество вариантов, из которых можно выбрать, значительно увеличивается!

  • 7+12+9 = 28
  • 10+7 = 17
  • 10+9 = 19
  • 7 + 12 = 19
  • 7+7 = 14
  • 7+9 = 16
  • 12+9 = 21

И по мере того, как мы продвигаемся вверх по индексам, варианты будут продолжаться и продолжаться, и продолжаться, и продолжаться ... Для этого индекса максимальная сумма равна 28, поэтому мы добавляем это во вспомогательный массив.

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

Индекс 5: Я не собираюсь перечислять здесь все варианты сумм, а вместо этого взгляну на схему. Ответом будет максимальная сумма по последнему индексу, в данном случае 33.

Но как это соотносится с остальной частью массива? В любой момент на самом деле есть только два варианта! Максимальная сумма - это либо предыдущая максимальная сумма и индекс перед (i-1), либо максимальная сумма в индексе перед этим (i-2) плюс значение индекса, в котором вы находитесь! Не верите мне? Попробуйте!

Если мы посмотрим на индекс в i-1, мы не сможем добавить значение, потому что i находится рядом с i-1. Если мы посмотрим на индекс в i-2, у нас уже есть максимальная сумма массива до этой точки, а затем мы можем добавить значение в i к этому максимуму. сумма. Рассмотрев оба этих варианта, мы четко выберем максимальное значение из этих двух.

Итак, давайте составим для этого формулу:

Чтобы использовать эту формулу, нужны два базовых случая. Нам нужно знать maxSums [0] и maxSums [1]. MaxSums [0] прост, потому что он всегда будет самим собой. MaxSums [1] также прост, потому что это всегда будет максимальное значение из первых двух чисел. Обладая этими знаниями, мы можем начать перебирать остальную часть массива и использовать формулу.

Решение

Мы начинаем с написания функции и заботимся о крайних случаях, когда входной массив имеет длину 0 или 1.

Теперь мы можем приступить к построению вспомогательного массива под названием maxSums. Мы можем сделать копию входного массива, а затем перезаписать значения по ходу. Мы находим максимальное значение первого и второго числа, как обсуждалось ранее, чтобы найти maxSums [1].

Теперь мы готовы начать цикл, начиная с i = 2, и применить нашу формулу из предыдущего.

Наконец, мы возвращаем последний элемент в массиве maxSums, и все готово!

Сложность времени и пространства

Временная сложность в этом случае довольно проста, поскольку нам нужно перебрать каждый элемент в массиве, дав нам время O (n), где n - длина массива. Учитывая пространство, мы создаем вспомогательный массив той же длины, что и ввод, который также даст нам O (n). Вы можете придумать способ оптимизировать пространство? Что, если бы мы отслеживали только два предыдущих maxSum? Хммммм… .. может быть, нам удастся получить постоянное место!

Попробуйте! Удачного взлома!