examples/perl/maxpathsum-bruteforce.plPerl
#!/usr/bin/perl

use warnings;

my @t;
push @t, [split ' '] for <STDIN>;

my $max=-INFINITY;
for my $x(0..2**@t-1)
{
	my $sum=0;
	my $i=0;
	for my $j(0..$#t)
	{
		$sum+=$t[$j][$i];
		$i+=$x % 2;
		$x=int($x/2);
	}
	$max=$sum if $sum>$max;
}
print "$max\n";

examples/perl/maxpathsum-recursive.plPerl
#!/usr/bin/perl

use warnings;

my @t;
push @t, [split ' '] for <STDIN>;

sub maxsum
{
	my ($j, $i)=@_;
	return -INFINITY if $i<0 or $i>$j;
	#print "($j $i)\n";
	return $t[0][0] unless $j;
	my $a=maxsum($j-1, $i-1);
	my $b=maxsum($j-1, $i);
	return $t[$j][$i]+($a>$b? $a: $b);
}

my $max=-INFINITY;
for my $i(0..$#t)
{
	my $sum=maxsum($#t, $i);
	$max=$sum if $sum>$max;
}
print "$max\n";

examples/perl/maxpathsum-recursive-memoize.plPerl
#!/usr/bin/perl

use warnings;

my @t;
push @t, [split ' '] for <STDIN>;
my @m;

sub maxsum
{
	my ($j, $i)=@_;
	return -INFINITY if $i<0 or $i>$j;
	return $t[0][0] unless $j;
	return $m[$j][$i] if defined $m[$j][$i];
	#print "($j $i)\n";
	my $a=maxsum($j-1, $i-1);
	my $b=maxsum($j-1, $i);
	return $m[$j][$i]=$t[$j][$i]+($a>$b? $a: $b);
}

my $max=-INFINITY;
for my $i(0..$#t)
{
	my $sum=maxsum($#t, $i);
	$max=$sum if $sum>$max;
}
print "$max\n";

examples/perl/maxpathsum-inductive.plPerl
#!/usr/bin/perl

use warnings;

my @s=(0);

while(<STDIN>)
{
	my @r=split ' ';
	$r[$_]+=$s[$s[$_-1]>$s[$_]? $_-1: $_] for 1..$#r-1;
	$r[$_]+=$s[$_] for -1, 0;
	@s=@r;
}

my $max=-INFINITY;
for(@s)
{
	$max=$_ if $_>$max;
}
print "$max\n";