matrixMax.rb

def max_contiguous_submatrix_n3(m)
  rows = m.count
  cols = rows ? m.first.count : 0

  vps = Array.new(rows)
  for i in 0..rows
    vps[i] = Array.new(cols, 0)
  end

  for j in 0...cols
    vps[0][j] = m[0][j]
    for i in 1...rows
      vps[i][j] = vps[i-1][j] + m[i][j]
    end
  end

  max = [m[0][0],0,0,0,0] 
  sum = Array.new(cols) 
  pos = Array.new(cols) 

  for i in 0...rows
    for k in i...rows
      sum.fill(0)
      pos.fill(0)
      local_max = 0
      sum[0] = vps[k][0] - (i==0 ? 0 : vps[i-1][0])
      for j in 1...cols
        value = vps[k][j] - (i==0 ? 0 : vps[i-1][j])
        if sum[j-1] > 0
          sum[j] = sum[j-1] + value
          pos[j] = pos[j-1]
        else
          sum[j] = value
          pos[j] = j
        end
        if sum[j] > sum[local_max]
          local_max = j
        end
      end
      
      if sum[local_max] > max[0]
        max = [sum[local_max], i, pos[local_max], k, local_max]
      end
    end
  end

  return max
end