Победить AlgoExpert: подматрица максимальной суммы

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

Сегодняшняя задача называется Подматрица максимальной суммы, и ее можно найти на AlgoExpert здесь. К сожалению, я не смог найти эту проблему ни на Leetcode, ни на HackerRank, поэтому приношу свои извинения читателям, у которых нет доступа.

Подсказка

Учитывая двумерную матрицу, наша цель — найти наибольшую подматрицу ширины и высоты, равных size. Гарантируется, что ширина и высота матрицы будут больше или равны size, а size будет положительным целым числом.

Например…

Как АлгоЭксперт решает проблему

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

Если мы посмотрим на индекс строки 1 и индекс столбца 1 в нашей матрице текущей суммы, мы получим текущую сумму 4, что мы получили бы, если бы мы сложили все числа слева и выше этой вершины (5+3+(-). 7)+3). Этот расчет стоит нам времени выполнения O(n) и пространственной сложности O(n).

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

Чтобы вычислить синий квадрат, мы можем взять сумму всей площади, представленной фиолетовым прямоугольником, которая, как мы знаем, равна 30, затем мы вычитаем площадь выше (оранжевый прямоугольник), которая равна 7, и площадь слева (красный прямоугольник), которая равна 7. равно 10. При этом одна площадь вычитается дважды, так как есть некоторое перекрытие, представленное зеленым прямоугольником на 5, затем мы добавляем это обратно и получаем в сумме 30–7–10+5 = 18. Это подтверждается, глядя на исходная сетка, и если мы добавим 3, 7, 8 и 0, мы также получим 18.

Осталось отследить макс и вуаля, очень простое и изящное решение. Но, как уже упоминалось, для этого требуется пространственная сложность O (n), и я покажу вам, как это преодолеть, кроме того, мы решим проблему за один проход.

Подход к проблеме

Представьте массив размером n, и вам нужно найти наибольшую сумму k последовательных чисел. Мы могли бы подойти к проблеме, построив массив текущей суммы, тогда каждый индекс в i ≥ k будет текущей суммой в индексе i за вычетом текущего sum по индексу ik, но было бы так же легко добавить следующее число и отбросить последнее в нашем первом прогоне, не создавая лишний массив. Например, для приведенного ниже массива размером k = 3:

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

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

Во-первых, расчет вертикальных сумм. Создаем массив той же ширины, что и матрица, заполненный нулями. Назовем этот массив verticalSums. По мере прохождения матрицы мы добавляем значение к соответствующему вертикальному индексу в verticalSums. Если индекс строки больше или равен size, мы можем вычесть вершину, которая находится над ней на size. Затем у нас будут соответствующие вертикальные суммы, которые нам нужно сложить или вычесть. Ниже мы можем увидеть, как выглядит этот массив после перебора каждой строки.

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

Примечание автора. Я также использую модель «точно в срок» для расчета вертикальной суммы, методологию, ставшую популярной в фабричной физике благодаря бережливому производству и производственной системе Toyota. Очень рекомендую вам ознакомиться с ним! Всегда полезно использовать другие ресурсы для управления процессом проектирования и разработки.

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

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

Наконец, мы будем использовать две дополнительные переменные: нашу max, которая будет максимальной суммой, которую мы видели во время итерации, и currentSum, которая является вычислением нашей области, которая нам нужна. знать. Каждый раз, когда мы начинаем новую строку в нашем итеративном процессе, мы сбрасываем нашу переменную currentSum в startRowSum, а затем добавляем и вычитаем соответствующую вертикальную сумму из нашей verticalSums массив. При каждом новом вычислении currentSum мы сравниваем его с max и при необходимости обновляем.