Instead of the dp solution, i made cumulative sum arrays both for x-direction wise and y-direction wise
namely xcum and ycum.
I also made 4 array of sets:
xsf(set iterating in x-direction and from i=0 to i=m-1)
xsb(set iterating in x-direction and from i=m-1 to i=0)
ysf(set iterating in y-direction and from i=0 to i=n-1)
ysb(set iterating in y-direction and from i=n-1 to i=0)
In the sets i inserted the -ve of the values of current element a[i][j] in consideration.
Explanation:
For any element, we have to anyway include its 4 neighboring cells and itself.
So what we can do to maximize the sum is take maximum cumulative array starting from the second adjacent cell to another cell in that row/column in all 4 directions.
If we consider the elements second to left of the cell (a[i][j]) in consideration the maximum value for that side is max( cum[i][j]+(maximum value in xsf[i] so far),0)
I did this for all 4 direction and all cells and took the maximum of all values.
Can anyone please point out any mistake in the approach?
My solution: https://www.codechef.com/viewsolution/18689116
Thanks in advance!