TADM2E 8.21

1

Sum every range and keep track of the maximum.

Given a set of numbers N = { x0, x1 ... xn }

M = 0

for i in (0 .. n)
  S[i, i] = xi
  for j in (i + 1 .. n)
    S[i, j] = S[i, j - 1] + xj
    if M < S[i, j]
      M = S[i, j]

2

Sum from each end, resetting the prefix or suffix (i.e., discarding the summed numbers) if it goes negative.

#!/usr/bin/perl

sub max_range
  {
  my @numbers = @_;

  my $prefix = 0;
  my $suffix = 0;

  for (my ($l, $r) = (0, @numbers - 1); $l <= $r; $l ++, $r --)
    {
    $prefix += $numbers[$l];
    $prefix = 0 if $prefix < 0;

    $suffix += $numbers[$r] if $l < $r;
    $suffix = 0 if $suffix < 0;
    }

  return $prefix + $suffix;
  }

my $max = max_range 31, -41, 59, 26, -53, 58, 97, -93, -23, 84;

print $max, "\n";