UniLecs #122_1. Максимальная подматрица
UniLecsЗадача: дана матрица N*M, состоящая из целых чисел. Необходимо определить подматрицу с максимальной суммой элементов в ней.
Входные данные: arr - матрица N*M, элементы матрицы целые числа по модулю меньше 1000. N,M - от 1 до 1000.
Вывод: максимальная сумма в подматрице исходной матрицы arr, а также координаты этой подматрицы.
Пример:
[ { -1, -2, -3 },
{ 1, 1, -4 },
{ 1, 1, -5 } ]
MaxSum = 4; SubMatrix Coordinate: (2, 1) - (3, 2)
(подматрица с левой верхней вершиной (2,1) и правой нижней (3,2), нумерация с 1).
Реализация:
- @pakrulin, JS: 0.7 балла за решение без комментариев и описания.
https://jsbin.com/hurogunoyo/edit?js,console
2. @lPestl, C#, F#: 1.1 балла
C#
https://gist.github.com/lpestl/328628faaca9a893ba767e88221f1b5b
F#
https://gist.github.com/lpestl/8fcabf2597eea893199c5ed26faa662c
3. @akolosov364, JS: 1 балл
Самое простое решение, проход по матрице и от каждой точки ищется подматрица с максимальной суммой. Очевидно решение не самое оптимальное.
https://gist.github.com/KolosovAO/2ad5a01394678526cd0a20db151dae38
Test:
https://repl.it/@AlieksieiKoloso/task122
4. @egormasharskii, C++: 1 балл
Перебираем пары строк O(N^2) и для каждого столбца ограниченного этими строками считаем сумму элементов. Далее можем применить алгоритм поиска подмассива с максимальной суммой на выходе которого имеем столбцы ограничивающие под-матрицу с максимальной суммой.
https://gist.github.com/myegor/f9dff7cd6c7b8c22ec9df705fee384e2
5. @tvolf, PHP: 1 балл
Суть алгоритма: перебираем все возможные варианты подматриц по оси x (первый и последний столбец, соответственно, xStart и xEnd). Затем интереснее. В промежуточном массиве prom, имеющем размерность высоты нашей исходной матрицы, накапливаем суммы по всем рядам в заданном диапазоне колонок (от xStart до xEnd). Далее, имея эти суммы элементов по рядам, используя алгоритм Кадейна (Kadane) для нахождения максимального подмассива в массиве, оставляем только ту последовательность рядов, которая дает максимальную подматрицу в диапазоне колонок от xStart до xEnd.
https://gist.github.com/tvolf/8c920263f17d3402683d917b4ee9e9a5
6. @dbond762, С++, C#: 1.1 балла
Перебираем все возможные размеры подматрицы. Далее смотрим все подматрицы данных размеров, и для каждой суммируем её элементы. (i1, j1) - (i2, j2) - координаты выходной подматрицы.
https://gist.github.com/dbond762/85ebe3aec19ea9586873f05762aaba41
Test C++:
https://repl.it/repls/OrangeAnchoredNature
Test C#:
https://repl.it/repls/DeepPaltryCharacterencoding
7. Антон, Rust: 1 балл
Находит отрезок во входной последовательности с максимальной суммой и саму максимальную сумму при помощи алгоритма Кадане. Возвращает None в случае, если входная последовательность пуста.
https://gist.github.com/AnthonyMikh/5792a78bbddffc4a0a6aeb09929c34d4
Test:
https://play.rust-lang.org/?gist=5377d01f52b5025c2f820ae80ff41087
8. @Zernov_A, Java: 1 балл
https://github.com/AlexZDeveloper/MaxSubMatrix
Test:
https://repl.it/@AlexZDeveloper/MaxSubMatrix
9. @LostInKadath, Python: 1.5 балла
The bruteforce solution is evident. We look through all the possible submatrices. For some speed optiization we use dynamic approach by calculating an extra-matrix of partial sums. The complexity of bruteforce is O(N*N * M*M).
The main idea of an optimized solution is to use a linear algorithm on one dimension, so we get O(N * M*M) complexity. We take a submatrix between two rows - rowStart and rowEnd. Then we summarize its columns in the partialSums array. And then we use O(n)-algorithm to find the subarray of maximal sum on it. Something like Kadane-algo, but Kadane returns 0 if all numbers in matrix are negative. This one returns a negative sum.
https://gist.github.com/LostInKadath/c15ead08d0a154cdef5a6b89f1c2db81
10. @jinxonik, Python: 1.5 балла
Метод 1. Простой перебор всех вариантов. Сложность O((N*M)^3). Возвращает максимальную сумму и координаты 4-х точек как (sum, (x1, y1), (x2, y2)).
Метод 2. Вычисляем все субматрицы subsum0, начинающиеся в точке (0,0), затем для нахождения суммы матрицы x1,y1-x2,y2 используем формулу subsum(x1,y1,x2,y2) = subsum0(x2,y2) + subsum0(x1-1,y1-1) - subsum0(x2,y1-1) - subsum0(x1-1,y2). Сложность O((N*M)^2). Возвращает максимальную сумму и координаты 4-х точек как (sum, (x1, y1), (x2, y2)).
https://gist.github.com/jin-x/55892a4625f4a6328baa844d6b04a09f
Test: