megeve is a software engineer at MindCoding. He is writing the online judge. Before starting to work, megeve decided to play one last game of MaxSquare (as always, megeve wants to beat his current highscore).
In MaxSquare the screen displays a square NxN matrix, A, whose elements are integers. The objective of the game is to quickly find the largest sum of numbers on the border of a square submatrix. As megeve's current highscore is one second, he wants you to write a program that finds this sum in less than one second.
Input
The first line of the input contains N. Thekth line (where 2 ≤ k ≤ N+1) line contains the description of the kth line (N numbers separated by spaces). Output
The first and only line of the output will contain the answer to megeve's problem. Please note that the answer may be negative.Constraints
1 ≤ N ≤ 50
-100 ≤ A[i][j] ≤ 100Sample
| Input | Output | Explanation |
|---|---|---|
| 4 1 1 1 1 5 5 5 1 5 1 5 1 5 5 5 1 | 40 | The maximal sum obtainable in the described manner is the one belonging to the subsquare whose border is made out of all the fives in the initial matrix. |
| 1 -1 | -1 |
Complexitate O(n4)
Se fixeaza un colt al patratului pe care il analizam (complexitate O(n2)) - cel mai simplu, cel din dreapta sus. Se mai fixeaza apoi si latura patratului. Cu aceste trei elemente determinate (coordonatele unui colt, respectiv latura patratului), acesta este unic determinat. Acum, tot ce mai avem de facut este sa iteram printre elementele conturului patratului selectat si sa le aflam suma. Fixarea lungimii laturii si iterarea printre elementele perimetrului sau iau inca O(n2) timp de executie, deci, complexitatea timp totala a acestei prime solutii este O(n4). Complexitate O(n3)
Cu o simpla observatie, putem reduce complexitatea solutiei de mai sus la O(n3). Observam ca daca avem un patrat cu colturile in (x1,y1), respectiv in (x2,y2), suma elementelor conturului sau se poate exprima ca suma a doua intervale de linii si a doua intervale de coloane. Concret, ne vom folosi de tehnica sumelor partiale pentru a reduce complexitatea rezolvarii de mai sus cu un ordin de N. Astfel, vom precalcula 2 matrici h[i][j] si v[i][j] dupa urmatoarea recurenta: h[i][j]=h[i][j-1]+mat[i][j] v[i][j]=v[i-1][j]+mat[i][j]unde
h[i][0]=0 si v[0][j]=0 Acum, in functie de implementare, este posibil sa avem un caz particular pentru subpatratele de latura 1. In general, suma conturului patratului cu colturile in (x1,y1), respectiv in (x2,y2) este h[x2][y2]-h[x2][y1-1]+h[x1][y2]-h[x1][y1-1]+v[x2-1][y2]-v[x1][y2]+v[x2-1][y2]-v[x1][y2] Formula de mai sus poate parea complicata, dar, daca cititorul va incerca sa o deduca singur o va intelege cu siguranta.
Asadar, aflarea sumei de pe contur a fost coborata de la O(n) la O(1) printr-o preprocesare in O(n2), aceasta neafectand insa complexitatea totala a algoritmului.
Complexitate totala: O(n3)
Lasam ca tema de gandire cititorului rezolvarea problemei in cazul in care avem lucram cu dreptunghiuri in loc de patrate in complexitate O(n4). Mentionez ca in acest caz exista o arie mult mai variata de cazuri particulare ce vor trebui tratate. O alta idee interesanta este rezolvarea problemei cu produse in loc de sume in O(n3) pentru cazul cu patrate (extensia pentru cazul cu dreptunghiuri devenind triviala ca idee in cazul in care deja se cunoaste solutia pentru problema cu sume pe dreptunghiuri).
