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)
4 4 | |
1 -9 -10 1 | |
-1 10 10 1 | |
0 9 9 -9 | |
-1 -1 -1 -1 |
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 |