Talk:To the Max

From Progteam

Jump to: navigation, search

C++ Solution

Here's Chein-I's C++ solution

http://cs.nyu.edu/~cil217/ICPC/2004GNYR/maxsum.cpp

Krystian's Advice

  • ) 1D solution is linear as previously discussed
  • ) 2D problem for a square (not rectangle) submatrix is a classical DP problem:

- in that kind of problems, I usually define a function with the 'right' (number of) parameters and then figure a recurrent formula - in this case the natual function seems to be f(i,j,k), i.e. the sum of all element in a given square, where (i,j) is a corner of the square, e.g. lower-left, and k is the square size - clearly, f(i,j,1) = m(i,j) - then f(i,j,k+1) = f(i+1,j+1,k) + m(i,j) + sum-of-m(i, j+1..j+k) + sum-of-m(i+1..i+k, j) - in order to compute f(i, j, k+1) in constant time, one could precompute compressed row and column matrices:

 mRow(i,j) = m(i, 1) + m(i, 2) + ... + m(i, j)
 mCol(i,j) = m(1, j) + m(2, j) + ... + m(i, ,j)

then

sum-of-m(a,b..c) = mRow(a,c) - mRow(a,b-1)
sum-of-m(a..b,c) = mCol(a,c) - mCol(b-1,c)

=> each f(i,j,k) could be computed in O(1), so we do

for k := 1 .. n-1  // all squares of size k+1
 for i := 1 .. n - k
    for j := 1 .. n - k
        compute f(i,j,k+1)

total time: O(n^3)

  • ) 2D problem for any submatrix

clearly, one could go for O(n^4) right away by adding an extra loop in the above algorithm in order to have rectangle rather than square submatrix

but could stick with O(n^3) by - solving O(n^2) instances of the 1D problem, where each instance is for a fixed rectangle width and rightmost column (of course, one could replace width with height, column with row, etc.) - note that for a fixed width W and rightmost column J we have the sequence

 sum-of-m(1, J-W+1..J), sum-of-m(2, J-W+1..J), ..., sum-of-m(n, J-W+1..J)

that sequence could easily be mainted in an array and updated for each instance or computed on the fly using the mRow and mCol matrices from above

Personal tools