Задача за намиране на подматрица с най-голям сбор от елементи
Пълното условие на проблема звучи така: дадена е N * N матрица, съдържаща положителни и отрицателни числа. Напишете кода за намиране на подматрицата с максималната възможна сума.
Има много решения на този проблем. Ще започнем с метода на груба сила и след това ще преминем към оптимизация.
Метод на груба сила: O(N⁶)
Подобно на други задачи за намиране на максимума, тази задача има просто решение. Достатъчно е да проверите всички подматрици, да изчислите сумата на всяка и да намерите най-голямата.
За да проверите всички подматрици и да избегнете повторения. Ще трябва да преминете през всички подредени двойки редове и след това през всички подредени двойки колони.
Това решение ще отнеме O(N⁶) време, тъй като има O(N4) матрици за проверка и отнема O(N²) време за проверка на една матрица.
Динамично програмиране: O(N⁴)
Имайте предвид, че предишното решение е бавно поради изчисляването на сумата от матричните елементи - O(N²) е много бавна операция. Може ли това време да се намали? да Можем да намалим времето за computeSum до O(1).
Погледнете следния правоъгълник:
Да предположим, че знаем следните стойности:
Всеки Val* започва от началото и завършва в долния десен ъгъл на подправоъгълника. За тези стойности знаем следното:
Тази информация ще ви позволи ефективно да изчислите тези стойности за всички точки на матрицата:
Възможно е предварително да се изчислят такива стойности и след това да се намери максималната подматрица. Следният код прилага този алгоритъм.
Оптимизирано решение: O(N³)
Невероятно, но има още по-добро решение. Ако имаме R реда и C колони, тогава проблемът може да бъде решен за O(R²C) време.
Спомнете си решението на задачата за намиране на максималния подмасив: замасив от цели числа (integer) намерете подмасива с максималната сума. Такъв максимален подмасив може да бъде намерен за O(N) време. Нека използваме това решение за нашата задача.
Всяка подматрица може да бъде представена като последователност от редове и последователност от колони. Можете да преминете през редовете и да намерите колоните, които дават максималната сума.
Кодът ще бъде така:
Сега остава въпросът: как да намерим "най-добрите" colStart и colEnd?
Трябва да намерим colStart и colEnd, които ни дават максималната възможна сума от всички подматрици rowStart отгоре и rowEnd отдолу. Можете да изчислите сумата на всяка колона и да използвате функцията maximumSubArray, обсъдена в началото на този проблем.
В предишния пример максималният подмасив покрива пространството от първата до четвъртата колона. Това означава, че максималният подмасив трябва да се простира от (rowStart, първа колона) до (rowEnd, четвърта колона).
Вече можем да напишем следния псевдокод:
Изчисляването на сумата на редове 5 и 6 отнема R*C време (тъй като изисква итерация от rowStart до rowEnd), което води до общо време за работа от O(R ³ C).
В редове 5 и 6 добавихме a[0]…a[i] от нулата, дори ако a[0]…a[i-1] бяха добавени в предишната итерация на външния цикъл. Да се отървем от двойната работа.
Пълната версия на кода изглежда така:
Това е изключително трудна задача. Малко вероятно е да успеете да разрешите такъв проблем на интервюто без помощта на интервюиращия.