HDU 1559 - Zui Da Zi Ju Zhen

Problem : Given N*M matrix. Find a x*y consequtive submatrix s.t. the sum of submatrix is maximum.
Solution : Set b[i][j]=sum(a[i][j], a[i][j+1], ..., a[i][j+y-1]). Then b[i][j]=b[i][j-1]-a[i][j-1]+a[i][j+y-1]. Thus using O(N*M) will get all the b elements. Set c[i][j]=sum(b[i][j], b[i+1][j], ..., b[i+x-1][j]). Then c[i][j]=c[i-1][j]-b[i-1][j]+b[i+x-1][j]. Thus using O(N*M) will get all the c elements. Since c[i][j] is the sum of x*y consequtive submatrix start from (i, j), get the maximum element of c is the answer.