Задача на поиск субматрицы с наибольшей суммой элементов

Полное условие задачи звучит так: дана матрица размером N*N, содержащая положительные и отрицательные числа. Напишите код поиска субматрицы с максимально возможной суммой.

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

Метод грубой силы: O(N⁶)

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

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

Это решение потребует O(N⁶) времени, так как необходимо проверить O(N⁴) матриц, а проверка одной матрицы занимает O(N²) времени.

Динамическое программирование: O(N⁴)

Обратите внимание, что предыдущее решение работает медленно из-за расчета суммы элементов матрицы — O(N²) — очень медленная операция. Можно ли сократить это время? Да! Мы можем уменьшить время computeSum до O(1).

Посмотрите на следующий прямоугольник:

Предположим, что нам известны следующие значения:

			ValD = area(point(0, 0) -> point(x2, y2))
ValC = area(point(0, 0) -> point(x2, yl))
ValB = area(point(0, 0) -> point(xl, y2))
ValA = area(point(0, 0) -> point(xl, yl))

Каждое Val* начинается в исходной точке и заканчивается в нижнем правом углу подпрямоугольника. Про эти значения мы знаем следующее:

			area(D) = ValD - area(A union С) - area(A union B) + area(A).

Или:

			area(D) = ValD - ValB - ValC + ValA

Данная информация позволит эффективно рассчитать эти значения для всех точек матрицы:

			Уа1(х, у) = Уа1(х-1, у) + Уа1(у-1, х) - Уа1(х-1, у-1)

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

			int getMaxMatrix(int[][] original) {
  int maxArea = Integer.MIN_VALUE; // Важно! Max может быть < 0
  int rowCount = original.length;
  int columnCount = original[0].length;
  int[][] matrix = precomputeMatrix(original);
  for (int rowl = 0; rowl < rowCount; rowl++) {
    for (int row2 = rowl; row2 < rowCount; row2++) {
      for (int coli = 0; coli < columnCount; coll++) {
        for (int col2 = coli; col2 < columnCount; col2++) {
          maxArea = Math.max(maxArea, computeSum(matrix, rowl, row2, coli, col2));
        }
      }
    }
  }
  return maxArea
}

int[][] precomputeMatrix(int[][] matrix) {
  int[][] sumMatrix = new int[matrix.length][matrix[0].length]; 
  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix.length; j++) {
      if (i == 0 && j == 0) { // первая ячейка
        sumMatrix[i][j] = matrix[i][j];
      } else if (j == 0) { // ячейка в первой колонке
        sumMatrix[i][j] = sumMatrix[i - l][j] + matrix[i][j];
      } else if (i == 0) { // ячейка в первом ряду
        sumMatrix[i][j] = sumMatrix[i][j-1] + matrix[i][j]; 
      } else {
        sumMatrix[i][j] = sumMatrix[i-l][j] +
        sumMatrix[i][j-1] - sumMatrix[i-l][j-1] + 
        matrix[i][j];
      }
    }
  }
  return sumMatrix;
}

int computeSum(int[][] sumMatrix, int il, int i2, int jl, int j2) {
  if (il == 0 && jl == 0) { // начинаем с ряда 0, колонки 0
    return sumMatrix[i2][j2];
  } else if (il == 0) { // начинаем с ряда 0
    return sumMatrix[i2][j2] - sumMatrix[i2][jl - 1];
  } else if (jl == 0) { // начинаем с колонки 0
    return sumMatrix[i2][j2] - sumMatrix[il-l][j2];
  } else {
    return sumMatrix[i2][j2] - sumMatrix[i2][jl-1] - sumMatrix[il-l][j2] + sumMatrix[il-1][jl-1];
  }
}

Оптимизированное решение: O(N³)

Невероятно, но существует еще более оптимальное решение. Если у нас есть R строк и С столбцов, то задачу можно решить за О(R²C) времени.

Вспомните решение задачи про поиск максимального субмассива: для массива целых чисел (integer) найдите субмассив с максимальной суммой. Такой максимальный субмассив можно найти за О(N) времени. Давайте используем это решение для нашей задачи.

Каждую субматрицу можно представить в виде последовательности строк и последовательности столбцов. Можно пройтись по строкам и найти столбцы, дающие максимальную сумму.

Код будет таким:

			maxSum = 0
foreach rowStart in rows
foreach rowEnd in rows
/* У нас есть количество возможных субматриц с границами 
* rowStart и rowEnd
* Найдите границы colStart и colEnd, дающие
* максимальную сумму. */
maxSum = max(runningMaxSum, maxSum)
return maxSum

Теперь остается вопрос: как найти «лучшие» colStart и colEnd?

Рассмотрим субматрицу:

Нам необходимо найти colStart и colEnd, которые дают нам максимально возможную сумму всех субматриц rowStart сверху и rowEnd снизу. Можно вычислить сумму каждого столбца и использовать функцию maximumSubArray, которая обсуждалась в начале решения этой задачи.

В предыдущем примере максимальный субмасив охватывал пространство с первой по четвертую колонку. Это означает, что максимальная субматрица должна простираться от (rowStart, первый столбец) до (rowEnd, четвертый столбец).

Теперь мы можем записать следующий псевдокод:

			maxSum = 0
foreach rowStart in rows
foreach rowEnd in rows
foreach col in columns
partialSum[col] = sum of matrix[rowStart, col] through
matrix[rowEnd, col]
runningMaxSum = maxSubArray(partialSum)
maxSum = max(runningMaxSum, maxSum)
return maxSum

Вычисление суммы в строках 5 и 6 занимает R*C времени (так как требует итерации от rowStart до rowEnd), что дает общее время выполнения О(R ³ C).

В строках 5 и 6 мы добавляли a[0]…a[i] с нуля, даже если на предыдущей итерации внешнего цикла добавились a[0]…a[i-1]. Давайте избавимся от двойной работы.

			maxSum = 0
foreach rowStart in rows
clear array partialSum
foreach rowEnd in rows
foreach col in columns
partialSum[col] += matrix[rowEnd, col]
runningMaxSum = maxSubArray(partialSum)
maxSum = max(runningMaxSum, maxSum)
return maxSum

Полная версия кода выглядит так:

			public void clearArray(int[] array) {
  for (int i = 0; i < array.length; i++) {
    array[i] = 0;
  }
}

public static int maxSubMatrix(int[][] matrix) {
  int rowCount = matrix.length;
  int colCount = matrix[0].length;

  int[] partialSum = new int[colCount];
  int maxSum = 0; // Макс, сумма = 0 (матрица пуста)

  for (int rowStart = 0; rowStart < rowCount; rowStart++) {
    clearArray(partialSum);

    for (int rowEnd = rowStart; rowEnd < rowCount; rowEnd++) {
      for (int i = 0; i < colCount; i++) {
        partialSum[i] += matrix[rowEnd][i]j
      }

      int tempMaxSum = maxSubArray(partialSum, colCount);

      /* Если вы хотите отслеживать координаты, добавьте
       * код здесь, чтобы сделать это. */
      maxSum = Math.max(maxSum, tempMaxSum);
    }
  }
  return maxSum;
}

public static int maxSubArray(int array[], int N) {
  int maxSum = 0;
  int runningSum = 0;

  for (int i = 0; i < N; i++) {
    runningSum += array[i];
    maxSum = Math.max(maxSum, runningSum);

    /*  Если runningSum < 0, нет смысла продолжать ряд
      * Сброс. */
    if  (runningSum < 0) {
      runningSum  = 0;
    }
  }
  return  maxSum;
}

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

Разбор задачи по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT-компанию»

Задачи повышенной сложностиПодписаться

13К открытий13К показов

Также рекомендуем

IT-задачи о кофе, switch и шумах

Собрали самые каверзные задачи на тему программирования по Go, C# и QA, которые удивили инженеров Ozon Tech, и делимся решениями.

Метаэвристические решения Задачи Коммивояжёра

В данной статье рассматриваем и реализуем на Python различные подходы (GA, ACO, SA) к решению задачи коммивояжёра.

Задачи с собеседований для разработчиков в IBM, Amazon и Microsoft

Собрали отзывы о собеседованиях на должности разработчиков ПО в IBM, Amazon и Microsoft. Составили подборку задач и вопросов от HR.

Как я пытался писать красивый код

Недавно прошёл конкурс красоты кода. Участие по направлению Android в этом конкурсе было интересным опытом, которым я поделюсь в статье.