Сложность: средняя, ​​Запрошено: Facebook, Microsoft, Amazon, Morgan Stanley, Walmart, Flipkart, Hike, Oracle, Samsung, Snapdeal, Zoho

Основные выводы

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

Давайте разберемся в проблеме

Для массива X [] с n элементами нам нужно написать программу, чтобы найти максимальную сумму подмассива среди всех подмассивов. Подмассив массива X [] - это непрерывный сегмент от X [i] до X [j], где 0 ‹= i‹ = j ‹= n.

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

Примеры

Ввод: X [] = [-4, 5, 7, -6, 10, -15, 3], Выход: 16

Объяснение: Подмассив [5, 7, -6, 10] имеет максимальную сумму.

Ввод: X [] = [-3, 2, -1, 4, -2], Выход: 5

Объяснение: Подмассив [2, -1, 4] имеет максимальную сумму.

Вход: X [] = [5, 7, 6, 10, 3], Выход: 31

Объяснение: Все элементы массива неотрицательны. Таким образом, максимальная сумма подмассива будет суммой всего массива.

Обсуждаемые подходы к решению

  • Подход грубой силы с использованием трех вложенных циклов
  • Использование двух вложенных циклов
  • Использование подхода «разделяй и властвуй», аналогичного сортировке слиянием.
  • Использование динамического программирования
  • Алгоритм Кадане: использование одного цикла и переменных

Подход грубой силы с использованием трех вложенных циклов

Самое простое решение - исследовать все возможные подмассивы для всех i и j, где i≤j. Мы вычисляем сумму каждого подмассива и возвращаем максимум среди них.

Псевдокод решения

Анализ временной и пространственной сложности

Мы используем три вложенных цикла: исследуем все пары в двух внешних циклах и вычисляем текущую сумму во внутреннем цикле. Временная сложность = O (n³). Сложность пространства = O (1)

Использование двух вложенных циклов

Идея решения

Теперь критический вопрос: можем ли мы оптимизировать вышеупомянутый подход дальше? нужно ли использовать внутренний цикл? Давай подумаем!

Если мы внимательно понаблюдаем, мы можем легко вычислить сумму подмассива от i до j + 1, если мы знаем сумму подмассива от i до j. Таким образом, нет необходимости в самом внутреннем цикле для вычисления суммы каждый раз для каждой пары (i, j). Мы можем вычислить сумму подмассива, используя эту формулу Sum (i, j + 1) = Sum (i, j) + X [j + 1]. Используя эту формулу, для каждого значения i мы можем вычислить текущую сумму для всех значений j.

Псевдокод решения

Анализ временной и пространственной сложности

В приведенном выше коде всего два вложенных цикла. Временная сложность = O (n²), Пространственная сложность = O (1)

Использование идеи разделяй и властвуй, похожей на сортировку слиянием

Мы снова должны задать тот же вопрос: можем ли мы еще больше улучшить временную сложность? можем ли мы решить эту проблему, используя более мелкие подзадачи или подход «Разделяй и властвуй»? Давай подумаем!

Идея решения

Предположим, нам нужна максимальная сумма подмассива массива X [l… r]. Разделим массив на два равных подмассива - X [l… mid] и X [mid + 1… r]. Тогда максимальный непрерывный подмассив X [i… j] должен находиться в одном из следующих мест:

  • Полностью в левом подмассиве X [l… mid], где l ≤ i ≤ j ≤ mid.
  • Полностью в правом подмассиве X [mid + 1… r], где mid + 1 ≤ i ≤ j ≤ r
  • Подмассив, пересекающий среднюю точку, так что low ≤ i ≤ mid ≤ j ≤ r. Сюда входят некоторые крайние правые элементы левого подмассива и некоторые крайние левые элементы правого подмассива.

Мы можем найти максимальные подмассивы X [l… mid] и X [mid + 1… r] рекурсивно, потому что эти две подзадачи являются меньшими примерами проблемы поиска максимальной суммы подмассивов. Итак, теперь нам нужно вычислить максимальный подмассив, который пересекает среднюю точку и принимает максимум из всех трех возможностей.

Псевдокод решения

Реализация объединенной части: maxCrossingSum (X, l, mid, r)

Подмассив, пересекающий среднюю точку, состоит из двух подмассивов: X [i… mid] и X [mid + 1… j]. Итак, нам нужно найти максимальную форму подмассива X [i… mid] и X [mid + 1… j], а затем объединить их.

Эта идея работает следующим образом:

  • Сначала мы находим максимальную сумму подмассива левой половины X [l… mid]. Поскольку этот подмассив должен содержать X [mid], поэтому мы запускаем цикл, начиная с индекса i = mid до l, и рассматриваем каждый подмассив формы X [i… mid].
  • Мы инициализируем переменные max_leftSum, которые содержат максимальную сумму, найденную на данный момент в левой половине, и сумму переменных, содержащую сумму записей в X [i… mid].
  • Когда мы находим подмассив X [i… mid] с суммой значений, превышающей max_leftSum, мы обновляем max_leftSum до суммы этого подмассива.
  • Точно так же для правой половины X [mid + 1, r] мы запускаем цикл, начиная с индекса j = mid + 1 до r, и рассматриваем каждый подмассив формы X [mid + 1… r]. Мы инициализируем и сохраняем максимальную сумму, найденную на данный момент в правой половине, в переменной max_rightSum.
  • Наконец, мы добавляем max_leftSum + max_rightSum и возвращаем это значение.

Анализ временной и пространственной сложности подхода «разделяй и властвуй»

Для упрощения анализа мы предполагаем, что исходный размер задачи является степенью двойки, а T (n) - это временная сложность максимального подмассива входного размера n. Чтобы вычислить общую временную сложность, нам нужно добавить временные сложности разделения, владения и объединения частей.

  • Для базового случая (n = 1) алгоритм занимает постоянное время. Т (1) = O (1). Рекурсивный случай имеет место, когда n ›1.
  • Время Сложность разделения части = O (1), потому что нам нужно вычислить середину, чтобы разделить массив на две равные половины.
  • Временная сложность побеждающей части: входной размер каждой подзадачи составляет n / 2 элементов, поэтому мы тратим T (n / 2) времени на решение каждой. Нам нужно решить две подзадачи размера n / 2, поэтому общая временная сложность решения меньших подзадач составляет 2T (n / 2).
  • Временная сложность комбинированной части: два отдельных одиночных цикла работают в противоположном направлении, причем в худшем случае каждый цикл выполняется n / 2 раз. Таким образом, временная сложность этого этапа O (n).

Окончательное рекуррентное соотношение: T (n) = O (1), если n = 1, T (n) = 2 T (n / 2) + O (n), если n ›1

Это повторение аналогично повторению для сортировки слиянием. Как мы увидим из основного метода, это повторение имеет решение T (n) = O (n logn). Вы также можете вернуться к методу рекурсивного дерева сортировки слиянием, чтобы понять, почему решение должно быть O (n logn).

Сложность пространства = O (logn), для пространства стека рекурсивными вызовами (Подумайте!)

Использование динамического программирования

Идея решения

Возьмем массив maxSumEnd [] размера n, где каждый maxSumEnd [i] обозначает максимальную сумму подмассива, заканчивающуюся индексом i. Теперь, если мы знаем maxSumEnd [i-1], мы можем легко вычислить maxSumEnd [i]. Вот идеи:

  • maxSumEnd [i] всегда включает значение X [i].
  • Если (maxSumEnd [i -1] ›0), то мы должны включить maxSumEnd [i -1] для вычисления maxSumEnd [i], потому что X [i]‹ maxSumEnd [i-1] + X [i]. Итак, в этой ситуации maxSumEnd [i] = maxSumEnd [i-1] + X [i]
  • Если (maxSumEnd [i -1] ‹0), то мы должны игнорировать maxSumEnd [i -1] для вычисления maxSumEnd [i], потому что X [i]› maxSumEnd [i-1] + X [i]. Итак, в этой ситуации maxSumEnd [i] = X [i]
  • Более простым способом мы можем написать maxSumEnd [i] = max (maxSumEnd [i-1] + X [i], X [i])

Наконец, мы возвращаем максимальное значение, хранящееся в массиве maxSumEnd [], чтобы найти решение. Эта проблема подпадает под стратегию динамического программирования, потому что мы сохраняем решение подзадач и решаем большую проблему, используя решение меньшей подзадачи.

Действия по устранению

  1. Создайте дополнительный массив maxSumEnd [] размером n
  2. Инициализируйте массив базовым решением, например maxSumEnd [0] = A [0]
  3. Пройдите по массиву от i = 1 до n-1, и на любой i-й итерации выберите текущий элемент X [i] и вычислите maxSumEnd [i].
  • Если (maxSumEnd [i-1] ‹0), то maxSumEnd [i] = X [i]
  • В противном случае maxSumEnd [i] = X [i] + maxSumEnd [i-1]

4. Вернуть максимум суммы, хранящейся в массиве maxSumEnd [n].

Псевдокод решения

Анализ временной и пространственной сложности

Мы дважды обходим массив, используя один цикл. Итак, сложность времени = O (n). Сложность пространства = O (n), для дополнительного массива maxSumEnd [n]

Эффективный подход с использованием алгоритма Кадане

Идея решения

Теперь критический вопрос: можем ли мы решить проблему в пространстве O (1)? Более того, можем ли мы решить проблему за один обход? Вот оптимизированное решение с использованием известного алгоритма кадане:

  • Согласно описанному выше подходу, мы можем легко вычислить максимальную сумму подмассива, заканчивающуюся на i-м индексе, с помощью одного цикла. Сохраним это значение в переменной maxSum_endingHere.
  • Максимальная сумма подмассива будет максимальной из всех сумм подмассивов, заканчивающихся индексом i. Таким образом, мы можем отслеживать максимальную сумму подмассивов в переменной maxSum_so_far.
  • Во время каждой итерации, если (maxSum_endingHere ›maxSum_so_far), мы обновляем maxSum_so_far = maxSum_endingHere.
  • К концу цикла максимальное значение суммы подмассива сохраняется в переменной maxSum_so_far. Мы возвращаем это значение в качестве вывода.

В приведенной выше идее мы используем две дополнительные переменные и один обход. Без лишнего места, без двойного обхода! Отличная оптимизация.

Шаги решения

  1. Мы инициализируем переменные maxSum_so_far и maxSum_endingHere с помощью X [0].
  2. Мы запускаем цикл от i = 1 до n -1, где на каждой i-й итерации.
  • Вычислить максимальную сумму подмассива, оканчивающуюся i-м индексом в т.е maxSum_endingHere = max (maxSum_endingHere + X [i], X [i])
  • Обновите maxSum_so_far, т.е. если (maxSum_so_far ‹maxSum_endingHere), то maxSum_so_far = maxSum_endingHere.
  1. К концу цикла мы возвращаем maxSum_so_far.

Псевдокод решения

Анализ временной и пространственной сложности

Каждый элемент был посещен только один раз за один цикл. Мы также выполняем постоянную операцию на каждом шаге итерации цикла. Таким образом, временная сложность = O (n). Сложность пространства = O (1), мы используем только постоянное количество переменных.

Критические идеи думать!

  • Как мы можем оптимизировать вышеупомянутые алгоритмы, чтобы найти начальный и конечный индексы подмассива с максимальной суммой?
  • Какова временная сложность лучшего решения, если в качестве входных данных для этой проблемы используется отсортированный массив?
  • Можем ли мы использовать тот же подход, чтобы найти максимальный подмассив продукта?
  • Обрабатывают ли приведенные выше алгоритмы случай отрицательных чисел?

Сравнение временных и пространственных сложностей

  • Три вложенных цикла: Time = O (n³), Space = O (1)
  • Два вложенных цикла: Time = O (n²), Space = O (1)
  • Разделяй и властвуй: время = O (nlogn), Space = O (logn)
  • Динамическое программирование: время = O (n), пробел = O (n)
  • Алгоритм Кадане: время = O (n), пространство = O (1)

Похожие вопросы по кодированию для практики

  • Найдите максимальный подмассив продукта
  • Найдите сумму максимальных элементов каждого возможного подмассива
  • Вычислить подматрицу максимальной суммы размера k x k в матрице m x n
  • Самый длинный подмассив в двоичном массиве с равным количеством нулей и единиц
  • Непрерывный подмассив наибольшей суммы, содержащий только неотрицательные элементы

Наслаждайтесь обучением, наслаждайтесь кодированием, наслаждайтесь алгоритмами!

Первоначально опубликовано на веб-сайте EnjoyAlgorithms: «https://www.enjoyalgorithms.com/blog/maximum-subarray-sum Ана/