PROBLEM LINK:Setter Hasan Jaddouh DIFFICULTY:EASYMEDIUM PREREQUISITES:2D Arrays, Maximum Sum contiguous subarray of a 1D Array (i.e. Dynamic Programming ),Precalculation/Precomputation PROBLEM:Given a $2D$ 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 Precomputation of maximum possible sum of a contiguous subsequence (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 precompute the maximum contiguous subsequence sum for each row and column, in $4$ directions, namely, Up, Down, Left and Right. This can be done using the standard Maximum contiguous subsequence sum of a $1D$ array. All thats left is, to check each cell as a possible $centre$ of the $+$ and use precomputed 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 subsequence of $1D$ array" problem and then implement it. This editorial will focus more on intuition and how to deduce the problem to the said contiguous subproblem above. Implementation details can be seen in setter's solution. This editorial is having only a single section, as the approach is pretty much straightforward 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
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 subsequence sum part is taking an $O(N)$ time for each cell, making the solution time out. If we can, somehow, avoid recomputing the maximum contiguous subsequence sum again and again, we can get an AC. Turns out, we can easily precalculate the required contiguous subsequence sums getting rid of the TLE! What the setter did is, he made four $2D$ arrays (1 for each direction). A little note on them could be helpful in getting the intuition,
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 precomputation uses standard $1D$ array algorithm, which you can see from the link in prerequisite, 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 precomputation. 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[i1][j] + down[i+1][j] + left[i][j1] + 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 subsequence 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[i1][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 :) Editorialist's Solution will be put up on demand. $Time$ $Complexity$ $O(N*M)$ CHEF VIJJU'S CORNER :D1. Meaning of left[i][j] 2. Note on counting errors and using, say, up[i1][j] instead of up[i][j] 3. Setter's Notes 4. Tester's Notes 5. Some related practice problems are below
This question is marked "community wiki".
asked 26 May '18, 18:47

I suggest that instead of making 4 2D arrays for precomputation, we can make one 2D array. First we copy the original array to the pre[i][j]. Then for all 4 directions, we just update it. Also while calculating the pre[i][j] for the last direction we create a min variable=xxxxxxxxx,and while updating the pre[i][j] we just compare it with the each element and print the max. I think this would save a lot of memory as well as aa little time too. My solution https://www.codechef.com/viewsolution/18665680 answered 26 May '18, 23:49
1
Yes, that is also possible. I wanted to try it out, but I had no time, so had to stick with setter's solution. Thanks for sharing!!
(27 May '18, 00:01)

hey, It was a pretty straightforward explanation. Thank You. Would you also be kind enough to point out the mistake in my solution for first Subtask#1 for 20 points? Thanks in advance. I tried following brute force approach. You can find my code at https://www.codechef.com/viewsolution/18668975 answered 27 May '18, 15:55
Thank you :) . One of the few people who gave feedback on quality of editorial ^_^. Check out this Test case
(27 May '18, 17:50)
if the centre is at (1,2) ie 1, left arm till 1, right till 0, upper and down till 0. the sum of plus will be zero. @vijju123 Also, Many AC submission are also giving 0 as solution, example: https://www.codechef.com/viewsolution/18668969
(27 May '18, 18:06)
Sorry, my bad.
(27 May '18, 18:31)
Here.
(27 May '18, 19:04)
It was indeed that line and another line somewhere below it. I was checking 1 less index. Thank You.
(27 May '18, 19:19)

For those who are getting wrong answer on second testcase of first subtask, initialize ans = INT_MIN. Weak testcases. Consider this testcase: 2 3 4 2 2 2 2 2 2 2 2 2 2 2 2 3 3 2 2 2 2 2 2 2 2 2 Output should be: 12 10 But my code gives: 12 12 answered 27 May '18, 00:32
I feel your code suffers from runtime error and undefined behavior for that case. If thats true, we cant do much for that, as making cases against undefined behavior for too many instances seems tedious.
(27 May '18, 15:13)

Can anyone help me in this solution : answered 29 May '18, 17:28

although my code has O(n^2) complexity it is giving TLE!!! Thanks in advance! answered 07 Jun '18, 04:52

The editorial link in the problem page is incorrect.
Will ping @admin