# O(N^3) max submatrix sum

my $n = 15;

my @m = map { my @r = map { int(rand(19))-9 } 0..$n-1; \@r; } 0..$n-1;
print "m=\n",map { my $r = $m[$_]; "$_: @$r\n" } 0..$n-1;

my @s = map { my @r = map { 0 } 0..$n-1; \@r; } 0..$n;
for (my $c=0;$c<$n;$c++) {
    for (my $r=1;$r<=$n;$r++) {
	$s[$r][$c] = $m[$r-1][$c]+$s[$r-1][$c];
    }
}

my ($m_top,$m_bot,$m_left,$m_right,$m_sum)=(-1,-1,-1,-1,-1);

for (my $top=0;$top<$n;$top++) {
    for (my $bot=$top;$bot<$n;$bot++) {
	my ($left,$sum) = (-1,-1);
	for (my $right=0;$right<$n;$right++) {
	    $left = $right unless ($sum>0);
	    $sum = ($s[$bot+1][$right]-$s[$top][$right]) + (($sum>0)?$sum:0);
	    ($m_top,$m_bot,$m_left,$m_right,$m_sum) = 
		($top,$bot,$left,$right,$sum) 
		if (($sum>$m_sum) or ($m_top==-1))
	}
    }
}

print "top=$m_top bot=$m_bot left=$m_left right=$m_right sum=$m_sum\n";