#! /usr/bin/perl

#Gavin Saldanha, b3131-31
#Homework #5
#input RNA sequence is given as a single command line argument

%memo; #to optimize the performance
$seq = uc($ARGV[0]);
for($i = 0; $i < length($seq); $i++) {
	$base = substr($seq, $i, 1);
	if($base ne 'A' and $base ne 'C' and $base ne 'G' and $base ne 'U') {
		die("Invalid sequence. Only use A, C, G, and U.");
	}
}
print &N($seq, 0, length($seq) - 1) . "\n";

sub isComplement {
	my ($base1, $base2) = @_;
	return ($base1 eq 'A' and $base2 eq 'U')
		|| ($base1 eq 'C' and $base2 eq 'G')
		|| ($base1 eq 'G' and $base2 eq 'C')
		|| ($base1 eq 'U' and $base2 eq 'A');
}

sub max {
	my $max = @_[0];
	for(my $i = 1; $i < scalar(@_); $i++) {
		if(@_[$i] > $max) {
			$max = @_[$i];
		}
	}
	return $max;
}

sub N {
	my ($seq, $i, $j) = @_;
	
	if($i >= $j) {
		return 0;
	}
	elsif(exists($memo{($i, $j)})) {
		return $memo{($i, $j)}
	}
	
	my $delta = isComplement(substr($seq, $i, 1), substr($seq, $j, 1));
	my $x = 0;
	
	for(my $k = $i+1; $k < $j; $k++) {
		my $y = N($seq, $i, $k) + N($seq, $k+1, $j);
		if($y > $x) {
			$x = $y;
		}
	}
	
	my $a = N($seq, $i+1, $j-1) + $delta;
	my $b = N($seq, $i+1, $j);
	my $c = N($seq, $i, $j-1);
	my $z = max($a, $b, $c, $x);
	$memo{($i, $j)} = $z;
	return $z;
}