PROBLEM LINK:
Setter- Hasan Jaddouh
Tester- Jakub Safin
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY-MEDIUM
PRE-REQUISITES:
2-D Arrays, Maximum Sum contiguous subarray of a 1-D Array (i.e. Dynamic Programming ),Pre-calculation/Precomputation
PROBLEM:
Given a 2-D array of size N*M, you have to find the maximum value achievable by a + shaped pattern. The elements of the array can be negative.
QUICK EXPLANATION:
Key Strategy- Pre-computation of maximum possible sum of a contiguous sub-sequence (subarray) for each row and column, and then checking for each cell as a possible centre of + gets things done in O({N}^{2}).
We quickly pre-compute the maximum contiguous sub-sequence sum for each row and column, in 4 directions, namely, Up, Down, Left and Right. This can be done using the standard Maximum contiguous sub-sequence sum of a 1-D array. All thats left is, to check each cell as a possible centre of the + and use pre-computed data to find the value achieved by + shape in O(1). This leads to a O({N}^{2}) solution.
EXPLANATION:
This is a pretty much straightforward problem. The problem asks you to deduce that its an application of standard “Maximum sum of contiguous sub-sequence of 1-D array” problem and then implement it. This editorial will focus more on intuition and how to deduce the problem to the said contiguous sub-problem above. Implementation details can be seen in setter’s solution.
This editorial is having only a single section, as the approach is pretty much straight-forward and standard.
1. Setter’s Solution-
Lets start from the basics. How’d you write a brute force solution to this problem? One of the algorithms would be-
- For each cell A_{i,j} in the 2-D array, do the following-
- Set it as centre and compute the maximum contiguous sub-sequence sum in right direction.
- Compute the maximum contiguous sub-sequence sum in left direction
- Compute the maximum contiguous sub-sequence sum in upwards direction
- Compute the maximum contiguous sub-sequence sum in the downwards direction.
- Store the maximum value obtained and print it.
Clearly, this is O({N}^{3}) and a little bit hard to pass under 1sec time limit. Can we do something about it?
Note that, the maximum contiguous sub-sequence sum part is taking an O(N) time for each cell, making the solution time out. If we can, somehow, avoid re-computing the maximum contiguous sub-sequence sum again and again, we can get an AC.
Turns out, we can easily pre-calculate the required contiguous sub-sequence sums getting rid of the TLE!
What the setter did is, he made four 2-D arrays (1 for each direction). A little note on them could be helpful in getting the intuition,
- up[i][j] - Maximum sum contiguous sub-sequence of elements in upward direction, from rows 1,2,3,\dots,i More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[1][j], arr[2][j], \dots, arr[i][j]
- down[i][j] -Maximum sum contiguous sub-sequence of elements in downward direction, from rows i,i+1,i+2,,\dots,N More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[i][j], arr[i+1][j], \dots, arr[N][j]
- right[i][j]- Maximum sum contiguous sub-sequence of elements in right direction, from columns j,j+1,j+2,\dots,M More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[i][j], arr[i][j+1], \dots, arr[i][M]
Based on above, can you derive the meaning of left[i][j] ? (answer will be in Chef Vijju’s Corner :D)
I highly stress that the meanings of each of these arrays are clear to you. The pre-computation uses standard 1-D array algorithm, which you can see from the link in pre-requisite, or check from setter’s solution. Discussing it would be redundant in the editorial.
The next part is, deriving answer for the + shape centered at A_{i,j} from this pre-computation. If the meaning of the above arrays are clear to you, it will not be hard at all!
Let Ans_{i,j} represent the maximum value of the + sign centered at cell A_{i,j}. Then, we can say that-
Ans_{i,j}= up[i-1][j] + down[i+1][j] + left[i][j-1] + right[i][j+1] + \underbrace{arr[i][j]} _ {Adding\space value\space at\space centre\space of\space +}
What this formula does is, it will find the maximum contiguous sub-sequence sum in all four directions, excluding the cell A_{i,j}. The meaning of arrays representing directions (Eg- up[i][j]) is already given above, and you can refer to that for interpretation purposes. Note that, we used up[i-1][j] instead of up[i][j] &etc. to avoid counting errors for element at centre. (Think a little about it. A more detailed explanation is given in my corner 
At last, we will print the maximum Ans_{i,j} we get, and print it
SOLUTION:
For immediate availability of setter and tester’s solution, they are also pasted in the tabs below. This is for your reference, and you can copy code from there to wherever you are comfortable reading them. You now dont have to wait for @admin to link solutions
Click to view
#include <iostream>
#include <algorithm>
#include <string>
#include <assert.h>
using namespace std;
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
assert(cnt>0);
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
int up[1010][1010];
int dn[1010][1010];
int lft[1010][1010];
int rgt[1010][1010];
int n,m;
int arr[1010][1010];
int T;
int sm_n=0,sm_m=0;
int main(){
//freopen("05.txt","r",stdin);
//freopen("05o.txt","w",stdout);
T=readIntLn(1,100);
while(T--){
n=readIntSp(3,1000);
m=readIntLn(3,1000);
sm_n += n;
sm_m += m;
assert(sm_n <= 1000);
assert(sm_m <= 1000);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(j==m){
arr[i][j] = readIntLn(-100000,100000);
} else {
arr[i][j] = readIntSp(-100000,100000);
}
}
}
for(int i=1;i<=n;i++){
lft[i][1] = arr[i][1];
for(int j=2;j<=m;j++){
lft[i][j] = max(lft[i][j-1] + arr[i][j],arr[i][j]);
}
}
for(int i=1;i<=n;i++){
rgt[i][m] = arr[i][m];
for(int j=m-1;j>=1;j--){
rgt[i][j] = max(rgt[i][j+1] + arr[i][j],arr[i][j]);
}
}
for(int j=1;j<=m;j++){
up[1][j] = arr[1][j];
for(int i=2;i<=n;i++){
up[i][j] = max(up[i-1][j] + arr[i][j],arr[i][j]);
}
}
for(int j=1;j<=m;j++){
dn[n][j] = arr[n][j];
for(int i=n-1;i>=1;i--){
dn[i][j] = max(dn[i+1][j] + arr[i][j],arr[i][j]);
}
}
int sol = -1ll<<30;
for(int i=2;i<=n-1;i++){
for(int j=2;j<=m-1;j++){
sol = max(sol, up[i-1][j] + dn[i+1][j] + lft[i][j-1] + rgt[i][j+1] + arr[i][j]);
}
}
cout<<sol<<endl;
}
assert(getchar()==-1);
}
Click to view
#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge
using cat = long long;
#ifdef DONLINE_JUDGE
// palindromic tree is better than splay tree!
#define lld I64d
#endif
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
cout << fixed << setprecision(10);
int T;
cin >> T;
for(int t = 0; t < T; t++) {
int N, M;
cin >> N >> M;
vector< vector<int> > G(N, vector<int>(M));
for(int i = 0; i < N*M; i++) cin >> G[i/M][i%M];
vector< vector<cat> > mx_up(N, vector<cat>(M));
vector< vector<cat> > mx_down(N, vector<cat>(M));
vector< vector<cat> > mx_lft(N, vector<cat>(M));
vector< vector<cat> > mx_rt(N, vector<cat>(M));
for(int i = 0; i < N; i++) {
cat mi = 0, sum = 0;
for(int j = 0; j < M; j++) {
if(j > 0) mx_lft[i][j] = sum-mi;
mi = min(mi, sum);
sum += G[i][j];
}
mi = sum = 0;
for(int j = M-1; j >= 0; j--) {
if(j < M-1) mx_rt[i][j] = sum-mi;
mi = min(mi, sum);
sum += G[i][j];
}
}
for(int i = 0; i < M; i++) {
cat mi = 0, sum = 0;
for(int j = 0; j < N; j++) {
if(j > 0) mx_up[j][i] = sum-mi;
mi = min(mi, sum);
sum += G[j][i];
}
mi = sum = 0;
for(int j = N-1; j >= 0; j--) {
if(j < N-1) mx_down[j][i] = sum-mi;
mi = min(mi, sum);
sum += G[j][i];
}
}
cat ans = -OVER9000;
for(int i = 1; i < N-1; i++) for(int j = 1; j < M-1; j++)
ans = max(ans, G[i][j] + mx_down[i][j] + mx_up[i][j] + mx_lft[i][j] + mx_rt[i][j]);
cout << ans << "\n";
}
return 0;}
// look at my code
// my code is amazing
Editorialist’s Solution will be put up on demand.
Time Complexity- O(N*M)
CHEF VIJJU’S CORNER 
1. Meaning of left[i][j]-
Click to view
left[i][j]- Maximum sum contiguous sub-sequence of elements in left direction, from columns 1,2,3, \dots,j More formally, it represents the maximum sum obtained by adding a contiguous sub-sequence of elements from list of arr[i][1], arr[i][2], \dots, arr[i][j]
2. Note on counting errors and using, say, up[i-1][j] instead of up[i][j]
Click to view
The value of element at the centre MUST be a part of the value/answer. We cannot say for certain, however, that it will be included in maximum contiguous sub-sequence sum for any direction. Maximum sub-array algorithm will, chose an element only if it maximizes the sum in that direction. It nowhere guarantees that the element we are using as centre will be picked. It is possible that none of the four include it in maximum sum calculation for the respective directions (undercount error) and its also possible that ALL of them count it while calculating the sum (overcount error).
3. Setter’s Notes-
Click to view
Try each possible center, for each one you should find maximum sum in each direction, naively this is O({N}^{3}) (assuming N=M), but you can precalculate the max sum from each cell to each of the 4 direction using similar idea to standard problem "maximum sum sub-array 1-D"
4. Tester’s Notes-
Click to view
O(N*M) algorithm would be to compute the max. sum going up/down/left/right by applying the standard linear time algorithm to each row/column and then compute the answer by trying all central cells and adding the max. in each direction.
5. Some related practice problems are below-
- Painting a Town - A challenging problem from ICPC-Kharagpur regions. Needs knowledge of DFS on a matrix, and probability as well.