*A. MaxSubSum*

Algoritmul general de găsire al submatricei de sumă maximă este prea încet pentru această problemă, având complexitate O(N ^ 3). Este în schimb natural să ne gândim că putem obţine o soluţie mai rapidă dacă analizăm modul de construcţie al matricei. Astfel, analizând matricea cu colţurile (x1, y1, x2, y2), observăm că suma sa este (x2 - x1 + 1) * B[y1...y2] + (y2 - y1 + 1) * A[x1...x2], unde prin T[a...b] am notat suma T[a] + T[a + 1] + …. T[b]. Această formulă ne arată, printre altele, că nu este întotdeauna optim să alegem independent liniile şi coloanele matricei bazându-ne pe subsecvenţele de sumă maximă din cele două şiruri (soluţie încercată iniţial de unii concurenţi). Uneori, o subsecvenţă de sumă nemaximă, dar de lungime mare, poate fi de ajutor.

Algoritmul general de determinare a submatricei de sumă maximă este prea încet pentru această problemă, având complexitate O(N ^ 3). Este în schimb natural să ne gândim că putem obţine o soluţie mai rapidă dacă analizăm modul de construcţie al matricei. Astfel, analizând matricea cu colţurile (x1, y1, x2, y2), observăm că suma sa este (x2 - x1 + 1) * B[y1...y2] + (y2 - y1 + 1) * A[x1...x2], unde prin T[a...b] am notat suma T[a] + T[a + 1] + …. T[b]. Această formulă ne arată, printre altele, că nu este întotdeauna optim să alegem independent liniile şi coloanele matricei bazându-ne pe subsecvenţele de sumă maximă din cele două şiruri (soluţie încercată iniţial de unii concurenţi). Uneori, o subsecvenţă de sumă nemaximă, dar de lungime mare, poate fi de ajutor.

În schimb, este adevărat că dacă submatricea optimă va avea X linii şi Y coloane, ne intereseaza doar subsecvenţele de lungime X, respectiv Y care au suma maximă posibilă în A şi B. Putem precalcula uşor şirul bestA[Length] = “suma maximă a unei subsecvenţe din A de lungime Length” în timp O(N ^ 2), analog pentru şirul bestB[]. Apoi vom itera peste toate cele N ^ 2 dimensiuni posibile ale submatricei şi vom reţine maximul expresiei LineCount * bestB[ColumnCount] + ColumnCount * bestA[LineCount].