Подмассив с наибольшей суммой элементов или алгоритм Кадане для вектора и матрицы

В типичной постановке задача звучит так:

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

Лучше, чем алгоритмом Кадане с временной сложностью O(n) сделать вряд ли возможно.

Вот реализация, проверенная в консоли текущей сборки Visual Studio 2019:

#include <iostream>
#include <iterator>
#include <cstdint>

template <class InputIterator> 
intmax_t maxsum(InputIterator first, InputIterator last) {
 intmax_t maxsofar = 0, maxendinghere = 0;
 for (; first != last; ++first) {
  maxendinghere = std::max (maxendinghere + (intmax_t)(*first), (intmax_t)0);
  maxsofar = std::max (maxsofar, maxendinghere);
 }
 return maxsofar;
}

int main() {
 int a[] = { -1,1,2,3,4,0,-55,6,3 };
 std::cout << maxsum(std::begin(a), std::end(a)) << std::endl;
}

Намного ли ухудшится производительность, если мы захотим найти максимальную сумму прямоугольного подмассива в двумерном массиве (матрице) и определить границы этого подмассива?

У меня не получилось лучше, чем O(n³), ведь суммы алгоритмом Кадане придётся считать внутри двойного цикла, выбирающего нужные столбцы матрицы.

Исходный алгоритм не хранил информацию об индексах элементов, ограничивающих искомый подмассив, в реализацию для матрицы это добавлено. Также для простоты использован обычный тип данных int *, а не шаблон.

Среда выполнения была той же.

#include <iostream>
#include <climits> /* INT_MIN */
#include <cstring> /* memset */

int kadane(int* arr, int* start, int* finish, int n) {
 //Каданеподобный алгоритм для простого массива целых с сохранением
 //индексов начала и конца цепочки в *start, *finish
 int sum = 0, maxSum = INT_MIN, 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 > maxSum) {
   maxSum = sum;
   *start = local_start;
   *finish = i;
  }
 }
 if (*finish != -1) return maxSum; //был хотя бы один неотрицательный
 maxSum = arr[0]; //если все отрицательные
 *start = *finish = 0;
 for (i = 1; i < n; i++) {
  if (arr[i] > maxSum) {
   maxSum = arr[i];
   *start = *finish = i;
  }
 }
 return maxSum; //то макс. элемент - это ответ
}

#define ROW 4
#define COL 5
 /* просто для примера, чтобы не возиться с размерностями */

void findMaxSum (int M[][COL], int & maxSum,
 int& finalTop, int& finalLeft, int& finalBottom, int& finalRight) {
 int left, right, i, temp[ROW], sum, start, finish;
 maxSum = INT_MIN;
 for (left = 0; left < COL; ++left) { //Взять левый столбец
  memset(temp, 0, sizeof(temp));
  for (right = left; right < COL; ++right) { //Взять правый столбец
   for (i = 0; i < ROW; ++i) temp[i] += M[i][right];
    //Вычислить суммы между левым и правым столбцами для строк
   sum = kadane (temp, &start, &finish, ROW); //найти начало и конец нужной цепочки
   if (sum > maxSum) { //сохранить индексы, если нужно
    maxSum = sum; 
    finalLeft = left; finalRight = right; finalTop = start; finalBottom = finish;
   }
  }
 }
}

int main() {
 int M[ROW][COL] = { 
  { 1, 2, -1, -4, -20 },
    //искомая подматрица окружена пробелами:
  {-8,      -3, 4, 2,     1 },
  { 3,       8,10, 1,     3 },
  {-4,      -1, 1, 7,    -6 } 
 };
 int r1,c1,r2,c2,ms;
 findMaxSum(M,ms,r1,c1,r2,c2);
 std::cout << "From indexes (" << r1 << ", " << c1 << ")" << 
  " to (" << r2 << ", " << c2 << ")" << std::endl;
 std::cout << "Max sum is: " << ms << std::endl;
 return 0;
}

28.01.2022, 20:02 [716 просмотров]