Как я завалил собеседование в Twitter

У вас проблема с «убиранием излишек», прогоните тест на 0,9,8,7,6,5,4,3,2,1,0,1
Сам на подобные грабли наступил ;)

Как я завалил собеседование в Twitter

upd

#!/usr/bin/perl

use strict;
use warnings;

print '10 ' . DoIt((2,5,1,2,3,4,7,7,6)) ."\n";
print '17 ' . DoIt((2,5,1,3,1,2,1,7,7,6)) ."\n";
print '42 ' . DoIt((4,3,1,5,8,0,4,0,0,5,5,7,5,8,3,3)) ."\n";
print '0 ' . DoIt((0,1,2,3,4,5,6,7,8,9,0)) ."\n";
print '0 ' . DoIt((0,9,8,7,6,5,4,3,2,1,0)) ."\n";
print '45 ' . DoIt((0,9,8,7,6,5,4,3,2,1,0,9)) ."\n";
print '1 ' . DoIt((0,9,8,7,6,5,4,3,2,1,0,1)) ."\n";
print '9 ' . DoIt((7,1,7,2,5)) ."\n";
print '2 ' . DoIt((1,0,7,0,1)) ."\n";
print '44 ' . DoIt((4,3,1,5,8,0,4,0,0,5,5,7,5,8,3,1,3,3)) ."\n";

sub DoIt {
    my $pool = 0;
    my $border = 0;
    my $capacity = 0;
    my $n = $#_ + 1;

    foreach my $val (@_) {
        $n --;
        if ($val < $border && $n > 0) {
            $pool += $border - $val;
            next;
        }
        elsif ($val < $border && $n <= 0) {
            $pool = 0;
            foreach my $rev_val (reverse @_) {
                $pool += $val - $rev_val if $rev_val < $val;
                last if $rev_val > $val;
            }
        }
        $border = $val;
        $capacity += $pool;
        $pool = 0;
    }
    return $capacity;
}

Как я завалил собеседование в Twitter

Закостылил решение с одним проходом

Perl

use strict;
use warnings;

print '1 ' . DoIt((0, 9, 8, 5, 1, 0, 1)) ."\n";
print '9 ' . DoIt((7, 1, 7, 2, 5)) ."\n";
print '10 ' . DoIt((2,5,1,2,3,4,7,7,6)) ."\n";
print '17 ' . DoIt((2,5,1,3,1,2,1,7,7,6)) ."\n";
print '42 ' . DoIt((4, 3, 1, 5, 8, 0, 4, 0 ,0 , 5, 5, 7, 5, 8, 3, 3)) ."\n";

sub DoIt {
    my $pool = 0;
    my $border = 0;
    my $capacity = 0;
    my $n = $#_ + 1;

    foreach my $val (@_) {
        $n --;
        if ($val < $border) {
            unless ($n <= 0) {
                $pool += $border - $val;
                next;
            } else {
                $pool = 0;
                foreach my $rev_val (reverse @_) {
                    $pool += $val - $rev_val;
                    last if $rev_val < $val;
                }
            }
        }
        $border = $val;
        $capacity += $pool;
        $pool = 0;
    }
    return $capacity;
}