#!/usr/bin/perl

my $seed = shift || time;
print "Seed: $seed\n";
srand $seed;

my $N = 10;
my $S = 20;
my @array = (undef);
for (1.. $N) { push @array, int(rand($S) - $S/2) }

parray(@array);
print "---\n";

#
# Algorithm starts here
#

my (@lval, @rval);
my ($left_total, $right_total) = (0, 0);
my ($left_min, $right_min) = (0, 0);

# I'm O(n)
for (1 .. $N) {
  $left_total += $array[$_];
  $left_min = $left_total if $left_total <= $left_min;
  $right_total += $array[$N-$_+1];
  $right_min = $right_total if $right_total <= $right_min;
  $lval[$_]    = -$left_min;
  $rval[$N-$_+1] = -$right_min;
}
$lval[0] = $rval[$N+1] = 0;
#parray(@lval);
#parray(@rval);
#print "---\n";

my $maxval = 0;
my $maxpos;
# I'm also O(n)
for (0 .. $N) {
  my $total = $lval[$_] + $rval[$_+1];
  if ($total > $maxval) {
    $maxval = $total;
    $maxpos = $_;
  }
}

# I could avoid these loops by storing some extra information
# But I was too lazy to complicate the program by doing so
# In any case they are both O(n).
my ($left, $right) = ($maxpos, $maxpos+1);
$left-- while $lval[$left-1] == $lval[$left] && $left > 0;
$right++ while $rval[$right+1] == $rval[$right] && $right < $N+1;
$left++;
$right--;

print "I think the best sequence is from $left to $right\n";
# Finished in O(n) time.
parray(@array);
my $maxsum = 0;
for (0 .. $N) {
  if ($_ >= $left && $_ <= $right) {
    print "*****";
    $maxsum += $array[$_];
  } else {
    print "     ";
  }
}
print "\n";
print "Total is: $maxsum\n";

sub parray {
  my @a = @_;
  for (@a) {
    if (defined $_) {
      printf "%4d ", $_;
    } else {
      printf "%4s ", "--";
    }
  }
  print "\n";
}