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!