README.md

Largest submatrix problem

A problem found on Linkedin.

Find the submatrix with the largest sum.

Example given:

A =

   1  -9 -10   1
  -1  10  10   1
   0   9   9  -9
  -1  -1  -1  -1

Sum: 38 A(2:3,2:3)

input.txt

   4   4
   1  -9 -10   1
  -1  10  10   1
   0   9   9  -9
  -1  -1  -1  -1

submat.f90

program submat
  implicit none
  integer a(10,10),mem(10,10,10,10)
  integer m,n,i,neg_inf
  integer fmax,fmax_bounds(4)
  parameter (neg_inf=-1000000)
  mem=neg_inf
  read(*,*) m,n
  do i=1,m
    read(*,*) a(i,1:n)
  end do
  fmax=neg_inf
  print*,f(1,m,1,n)
  print*,fmax_bounds
contains
  recursive function f(i,k,j,l) result(y)
    integer i,k,j,l,y,f0,f1,f2,f3,f4
    if (i.gt.k.or.j.gt.l) then           ! out of bounds check
      y=neg_inf
    else if (mem(i,k,j,l)>neg_inf) then  ! memorization
      y=mem(i,k,j,l)
    else
      f0=sum(a(i:k,j:l))                 ! O(m*n)
      f1=f(i,k-1,j,l)
      f2=f(i,k,j,l-1)
      f3=f(i+1,k,j,l)
      f4=f(i,k,j+1,l)
      y=max(f0,f1,f2,f3,f4)
      mem(i,k,j,l)=y
    end if
    if (y>fmax) then
      fmax=y
      fmax_bounds=(/i,k,j,l/)
    end if
  end function f
end program submat