Максимальная сумма прямоугольного подмассива

Дан массив действительные числа, A[1..n,1..n], я хочу найти подмассив

B = A[i..j,s..t]

с 1 <= i <= j <= n, и 1 <= s <= t <= n

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

Но возможно ли это? Если да, то как? Если нет, то почему?

Я уже знаю алгоритм, который выполняется за O(n^3)времени, путем сокращения его до n(n+1)/2подзадач сложности O(n), но это кажется немного медленным. Я знаю, что оптимальный алгоритм будет работать за Omega(n)времени, но я надеюсь, что динамическое программирование можно будет использовать для его работы за O(n^2)времени. .

Резюме исходного вопроса

Я добавил этот раздел, потому что чувствовал, что некоторые люди неверно истолковали суть моего вопроса. Первоначальный вопрос был следующим:

1. Можно ли использовать динамическое программирование для решения вышеуказанной задачи за O(n^2)время? Если да, то как? Если нет, то почему?

Дополнительные вопросы:

Я добавил сюда новый вопрос.Позже может быть добавлено больше:

1. Чтобы использовать динамическое программирование, мне нужно использовать решения легко решаемых подзадач (иначе это спорный вопрос). Структура задачи такова, что если взять подмассив B = A[1..m,1..m]массива A[1..n,1..n] где m < n, то оптимальное решение для массива Bне лучше, чем в A, тривиально, поскольку то же самое решение допустимо в А. Поэтому, чтобы использовать динамическое программирование, разумно спросить: какова связь между оптимальным подмассивом A[1..i,1..i]и оптимальным подмассивом A[1? ..i+1,1..i+1]?