#!/usr/bin/perl
#------------------------------------------------------------------------------
# by Jan Engelhardt <jengelh [at] linux01 gwdg de>, 2004
#
# Aufruf:
#       ts.pl [size] [range]
#
#   size:  Größe des Arrays
#   range: Zahlen für den Array liegen im Bereich -RANGE ... RANGE-1
#
#   Defaults sind size=5, range=100
#
#------------------------------------------------------------------------------
use strict;
no strict "subs", "refs";

my $size = $ARGV[0] || 5;
my $range = $ARGV[1] || 100;
my(@A, $O, $P);
my %max;


#------------------------------------------------------------------------------
# Array befüllen
#------------------------------------------------------------------------------
print "A:";
for(my $i = 0; $i < $size; ++$i) {
    $A[$i] = int(rand($range) - ($range / 2));
    print " ", $A[$i];
}
print "\n";


#------------------------------------------------------------------------------
# Teilsummen finden
#
# LEN:  Länge des Subarrays
# SIZE: Größe von "A"
#
# Die möglichen Größen der Subarrays liegen zwischen: 1 ... SIZE
# Für einen (kontinuierlichen) Subarray der Länge LEN gibt es
#   SIZE-LEN+1 Positionierungsmöglichkeiten.
#
# Also:
#       LEN   Mgl. bei SIZE=5
#       1     5
#       2     4
#       3     3
#       4     2
#       5     1
# ----------------------------
#   E(len=1..5)(size-len+1)     [Sigma; LEN von 1 bis 5 für "size-len+1"]
# oder: size/2*(size+1)         Gauß'sche Formel
#
# Da (in diesem, meinem, Programm) alle Subarrays durchgeprüft werden,
# ist die Komplexität
#
#       O(size/2*(size+1))
#
# NACHTRAG Nov 05 2004: O() ist dabei nicht die wirkliche Komplexität, da
# auch &sum() abhängig von SIZE ist -- demnach ist $P die tatsächliche
# Komplexität (s.u.)
#
#------------------------------------------------------------------------------

for(my $len = 1; $len <= $size; ++$len) {
    for(my $pos = 0; $pos <= $size - $len; ++$pos) {
        print "Checking len=$len pos=$pos";
        my $c = &sum(@A[$pos..($pos+$len-1)]);
        printf "\t%10d\n", $c;
        if($c > $max{value}) {
            %max = (value => $c, len => $len, pos => $pos);
        }
        ++$O;
    }
}
print "Maximale Teilsumme: ", $max{value}, "\n";
printf "Segment: %d (%d) bis %d (%d)\n", $max{pos}, $A[$max{pos}],
    $max{pos}+$max{len}-1, $A[$max{pos}+$max{len}-1];

#------------------------------------------------------------------------------
# Komplexität bewiesen durch:
#
#   $O wird für jeden Durchlauf erhöht, je größer SIZE ist, desto höher muss
#   O liegen.
#
# Beweis (SIZE von 5 ... 10):
#
# $ (for((j=5;j<=10;++j)); do echo -- SIZE=$j; ts.pl $j; done) | grep Wert
#
# -- SIZE=5
# Theoretischer Wert von $O: 15
# Tatsächlicher Wert von $O: 15
# -- SIZE=6
# Theoretischer Wert von $O: 21
# Tatsächlicher Wert von $O: 21
# -- SIZE=7
# Theoretischer Wert von $O: 28
# Tatsächlicher Wert von $O: 28
# -- SIZE=8
# Theoretischer Wert von $O: 36
# Tatsächlicher Wert von $O: 36
# -- SIZE=9
# Theoretischer Wert von $O: 45
# Tatsächlicher Wert von $O: 45
# -- SIZE=10
# Theoretischer Wert von $O: 55
# Tatsächlicher Wert von $O: 55
#
#------------------------------------------------------------------------------

print "Theoretischer Wert von \$O: ", ($size + 1) * ($size / 2), "\n";
print "Tatsächlicher Wert von \$O: $O\n";

print "Theoretischer Wert von \$P: ", ($size ** 3), "\n";
print "Tatsächlicher Wert von \$P: $P\n";

#------------------------------------------------------------------------------
# Vergleich mit anderen Algorithmen:
#
# http://www.hib-wien.at/leute/wurban/informatik/MaxPartSums.pdf
#       Algorithm 1: O(n**3)
#       Es setzt den "O-Zähler" woanders an -- nämlich innerhalb von &sum().
#       Unser O-Zähler in &sum() wird hier P genannt.
#       Per experimenta und Regressionskurve ergibt sich:
#         P(.53 * n ** 2.68)
#------------------------------------------------------------------------------

sub sum {
    my $rv = 0;
    foreach (@_) { $rv += $_; ++$P; }
    return $rv;
}

#------------------------------------------------------------------------------