Подматрица с минимальной суммой элементов

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

Очевидно, что "нативный" полный перебор даст здесь вычислительную сложность порядка O(N⁴), применяя алгоритм Кадане для работы с одномерными массивами-столбцами, попробуем обойтись сложностью O(N³), кто меньше?

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

Консольная программа, показанная ниже, проверена в Visual Studio 2015.

#include <iostream> 
#include <iomanip> //для setw
#include <cstdlib> //для exit
#include <climits> //для INT_MAX
#include <windows.h> //для system
using namespace std;

void error(int n) {
 char *msg[] = {
  "OK. Normal shutdown",
  "Can't allocate memory for matrix!"
 };
 cout << endl << msg[n];
 system("pause>nul");
 exit(n);
}

void printMatrix(int **a, int n, int m) {
 for (int i = 0; i < n; i++) {
  cout << endl;
  for (int j = 0; j<m; j++) {
   cout << setw(5) << a[i][j];
  }
 }
}

int kadane (int* arr, int* start, int* finish, int n) {
 int sum = 0, minSum = INT_MAX, i;
 *finish = -1;
 int local_start = 0;
 for (i = 0; i < n; ++i) {
  sum += arr[i];
  if (sum > 0) {
   sum = 0;
   local_start = i + 1;
  }
  else if (sum < minSum) {
   minSum = sum;
   *start = local_start;
   *finish = i;
  }
 }
 if (*finish != -1) return minSum;
 minSum = arr[0];
 *start = *finish = 0;
 for (i = 1; i < n; i++) {
  if (arr[i] < minSum) {
   minSum = arr[i];
   *start = *finish = i;
  }
 }
 return minSum;
}

void findMinSumSubmatrix (int **M, int ROWS, int COLS, 
  int &finalTop, int &finalLeft, int &finalBottom, int &finalRight, int &minSum) {
 minSum = INT_MAX;
 int left, right, i;
 int *temp = new int [ROWS];
 if (!temp) error (1);
 int sum, start, finish;
 for (left = 0; left < COLS; ++left) {
  for (int k=0; k<ROWS; k++) temp[k] = 0; 
   //каждый раз temp сбрасывать в 0, можно быстрей через memset
  for (right = left; right < COLS; ++right) {
   for (i = 0; i < ROWS; ++i) temp[i] += M[i][right];
   sum = kadane(temp, &start, &finish, ROWS);
   if (sum < minSum) {
    minSum = sum;
    finalLeft = left; finalRight = right;
    finalTop = start; finalBottom = finish;
   }
  }
 }
 delete[] temp;
}

int main() {
 //Описание данных и выделение памяти для матрицы:
 const int ROWS = 4, COLS = 5;
 int **M = new int * [ROWS];
 if (!M) error (1);
 for (int i = 0; i < ROWS; i++) {
  M[i] = new int [COLS];
  if (!M[i]) error(1);
 }
 
 //Заполнение матрицы числами по списку:
 int k = 0;
 int V[ROWS*COLS] = { 
   1, 2, 3, 4, 5,
   6,-1,-2,-3, 7,
   8,-4,-5,-6, 9,
  10,11,12,13,14
 };
 for (int i = 0; i < ROWS; i++)
 for (int j = 0; j < COLS; j++) M[i][j] = V[k++];

 //Обработка и вывод:
 int finalTop, finalLeft, finalBottom, finalRight, minSum;
 findMinSumSubmatrix(M,ROWS,COLS, finalTop, finalLeft, finalBottom, finalRight, minSum);
 cout << endl << "Matrix:";
 printMatrix (M, ROWS, COLS);
 cout << endl << "from indexes (" << finalTop << "," << finalLeft << 
   ") to (" << finalBottom << "," << finalRight << "), min.sum = " << minSum;

 //Освобождение памяти и выход:
 for (int i = ROWS-1; i>-1; i--) delete[] M[i];
 delete[] M;
 error(0);
}

Вот что выводится для теста из листинга:

Matrix:
    1    2    3    4    5
    6   -1   -2   -3    7
    8   -4   -5   -6    9
   10   11   12   13   14
from indexes (1,1) to (2,3), min.sum = -21
OK. Normal shutdown

11.11.2018, 13:34 [2127 просмотров]