mss.pl

#!perl
# This program is for keeping the linear-time
# algorithm for the maximum segment sum problem.

use strict;
use 5.012;
use List::Util qw/sum/;

sub mss { # This is the O(n) algorithm
  my ($sum, $mss) = (0, 0);
  for (@_) {
    if ($sum+$_ >= 0) {
      $sum += $_;
      $mss = $sum if $sum > $mss;
    }
    else {
      $sum = 0;
    }
  }
  return $mss;
}

sub mss_default {
  my @x = @_;
  my $mss = 0;
  for my $i (0..@x-1) {
    for my $j ($i..@x-1) {
      my $sum = sum @x[$i..$j];
      $mss = $sum if $sum > $mss;
    }
  }
  return $mss;
}