Решение максимальной суммы подмассивов: суперупрощенное объяснение

Реализации Python и javascript для алгоритмов

Постановка проблемы

У вас есть массив из n чисел. Вам нужно найти наибольшую сумму последовательных чисел массива.

По сути, это поиск подмассива с наибольшей суммой.

Например, массив [1, 2, 3, 4] будет иметь наибольшую сумму = 10, которая является суммой массива в целом. Для массивов без отрицательных целых чисел максимальная сумма подмассива равна сумме самого массива.

Теперь, что происходит, когда у вас есть отрицательные целые числа?

Возьмите массив [-1, -3, 4, 2], где подмассив с максимальной суммой будет [4, 2] с суммой = 6.

Что происходит, когда у вас есть огромный массив? Как разработать алгоритм для решения этой проблемы?

Решение

На самом деле есть много разных способов сделать это. Позвольте мне логически разбить два подхода, чтобы помочь вам понять процесс мышления.

Решение 1

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

• Мы создаем все возможные подмассивы из основного массива.
• Затем мы проверяем сумму каждого подмассива и возвращаем максимальную сумму.

Довольно просто? Давайте сделаем пробный прогон, чтобы понять это лучше.

• Пусть массив будет [-1, 2, -5, 7]
• Чтобы создать все подмассивы этого массива, мы можем выбрать каждый элемент и создать подмассив со всеми остальными элементами в последовательности.
• Вот подмассивы- [-1], [-1, 2], [-1, -5], [-1, 7], [-1, 2, -5], [-1, 2, 7], [-1, -5, 7], [-1, 2, -5, 7], [2], [2, -5], [2, 7], [2, -5, 7], [-5], [-5, 7], [7]. Ах, очень утомительный процесс.
• С каждым созданным нами подмассивом мы можем проверить сумму и сохранить ее запись.
• Всякий раз, когда сумма превышает нашу предыдущую запись, мы обновляем значение.
• Как только мы пройдемся по всем подмассивам, записанная нами сумма будет искомым ответом.
• Если мы посмотрим на все подмассивы, то заметим, что [7, 2]имеет максимальную сумму, которая равна 9.

Давайте попробуем сделать это на двух разных языках программирования. Идея состоит не только в том, чтобы решить проблему, но и в том, чтобы изучить синтаксис и код Python и JavaScript. Я предполагаю, что у вас есть общее представление о том, как писать код: циклы for, операторы if-else, объявление переменных и использование функций. Если нет, ознакомьтесь с этими вещами, прежде чем читать код.

У нас слишком много циклов for, а это значит, что временная сложность — это плохо. В данном случае это O(n³), потому что нам нужно выполнить три цикла.

Решение 2

Чтобы сделать вещи эффективными в таких задачах, нам нужно подумать о способах уменьшить количество циклов.

Есть ли способ решить это с помощью одного цикла?

Должен быть какой-то трюк, который мы можем использовать, чтобы сделать это. Посмотрим, сможем ли мы построить мыслительный процесс.

• Если мы перебираем массив только один раз, это означает, что мы посещаем каждый элемент массива один раз.
• Давайте теперь соединим точки в обратном порядке. Чтобы найти наш ответ, нам нужно сначала найти подмассив, который будет иметь максимальную сумму.
• Нам обязательно нужно посетить каждый элемент один раз. Что вы можете сказать об этом элементе по отношению к подмассиву с максимальной суммой? Он либо принадлежит этому подмассиву, либо нет. Правильно?
• Если он принадлежит подмассиву с максимальной суммой, вы можете добавить его значение во временную переменную, где вы сохраняете и постоянно обновляете потенциальную максимальную сумму. Если это не так, вы можете просто проигнорировать его и перейти к следующему элементу.
• Если вы сделаете это по всему массиву, что вы получите? Сумма всех элементов, принадлежащих подмассиву с максимальной суммой = ответ, который мы ищем, и мы получаем его, запустив всего один цикл!
• Теперь у вас возникнет вопрос: как мы узнаем, что данный элемент принадлежит этому подмассиву?
• Предположим, что у нас есть массив из n элементов. Мы находимся в k-м элементе этого массива.
• Если этот k-й элемент является частью нашего максимального подмассива, что в нем будет особенного? Либо она будет больше, чем сумма элементов до k-1, либо максимальная сумма до k-1 + kth элемента будет больше.
• Вы заметили, как мы создаем подзадачу с помощью нашей логики?
• Максимальная сумма подмассива для этого массива, заканчивающегося k-м элементом, фактически является максимальной суммой подмассива массива до k-1-го элемента + k-го элемента (если k-й элемент положителен).
• В любой момент времени мы находим максимальную сумму подмассива для массива до k-го элемента. Когда мы достигнем n-го элемента, мы бы нашли ответ для всего массива.

Звучит запутанно? Ничего страшного. Если вы впервые сталкиваетесь с такой проблемой, это может быть немного сложно. Давайте сделаем пробный прогон с реальным массивом.

• Пусть массив равен [-1, 2, -5, 7], как в примере, который мы использовали в решении 1. Итак, нам нужно собрать сумму элементов, принадлежащих подмассиву с максимальной суммой (назовем его нашим целевым подмассивом).
• Мы запускаем только один цикл. Итак, сначала мы идем к -1, и это сам по себе подмассив с суммой = -1. Предположим, что -1 является частью нашего целевого подмассива. -1 теперь наша временная максимальная сумма.
• Далее идем к 2. Теперь он либо является частью нашего целевого подмассива, либо нет. Откуда мы это знаем? Если он является частью подмассива, он должен быть либо больше текущей максимальной суммы, либо должен быть добавлен к максимальной сумме. 2 > -1 + 2 = 1, что больше, чем наша текущая временная максимальная сумма. Итак, давайте обновим нашу временную максимальную сумму = 2. Это просто подтверждает, что наше предыдущее предположение о том, что -1 является частью целевого массива, неверно. Теперь предположим, что 2 является частью целевого массива.
• Давайте перейдем к следующему элементу, то есть -5. -5 явно меньше текущей максимальной суммы, которую мы имеем. Таким образом, мы можем игнорировать его и перейти к следующему элементу.
• Теперь давайте перейдем к следующему элементу, 7, который больше, чем текущая максимальная сумма = 2. 7 + 2 = 9, что также больше, чем наша текущая максимальная сумма. Это означает, что 7 является частью нашего целевого подмассива, и мы можем обновить нашу максимальную сумму = 9.
• Мы достигли конца массива, и решение, к которому мы пришли, это 9, что является требуемым ответом, и мы только что использовали один цикл!

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

В конце мы получим требуемый ответ.

Вот реализация кода в javascript и python для этого подхода:

Поскольку мы используем только один цикл, временная сложность равна O(n).

Некоторые наблюдения

• Я запустил обе эти программы в Leetcode для соответствующего вопроса (решение 2).
• Программа javascript выполнялась меньше времени, чем код python.
• Однако python занимал меньше памяти, чем javascript.

Ключевые выводы

• Если вы столкнетесь с похожей проблемой на собеседовании, подумайте о том, как вы пытаетесь найти решение.
• Возьмите образец тестового примера и выполните пробный прогон, как я сделал здесь в первую очередь.
• И после этого вы можете кодировать его.
• Если вы столкнулись с такой проблемой в онлайн-тестировании, использование javascript вместо python может помочь вам занять более высокое место в рейтинге, поскольку он быстрее.
• Когда вы имеете дело с массивами и замечаете, что вам нужно выполнить итерацию по массиву, вам следует подумать об использовании наименьшего количества циклов for.
• Оттуда подумайте о том, что вы можете сделать, как вы можете отслеживать полезную информацию, проходя через каждый элемент массива.
• В таких задачах мы обычно хотели бы отслеживать две переменные: текущее значение, которое мы вычисляем на каждой итерации, и максимальное или минимальное значение, которое будет окончательным ответом, который постоянно обновляется по мере прохождения массива.

Fundamental Approach: A summary.
1. Have a single for loop.
2. Calculate a currentValue for each element in the array based on the question.
3. Then update the maxValue as max(maxValue, currentValue)
4. Vice-versa for minValue.

Попробуйте решить этот вопрос Leetcode самостоятельно, не видя никаких ссылок после прочтения этой статьи, и проверьте свое понимание.

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