Instantly share code, notes, and snippets.

Last active November 29, 2020 21:30
Show Gist options
• Save hholst80/6b75dac920b76d89544f6d3f111f689a to your computer and use it in GitHub Desktop.

# Largest submatrix problem

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)

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 4 4 1 -9 -10 1 -1 10 10 1 0 9 9 -9 -1 -1 -1 -1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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