Quick solution to http://qandwhat.apps.runkite.com/i-failed-a-twitter-interview/

gistfile1.php

<?php
function fill(array $in)
{
    foreach ($in as $i => $h) {
        $m[$i] = max(
            min(
                array_reduce(array_slice($in, 0, $i), 'max'),
                array_reduce(array_slice($in, $i), 'max')
            ) - $h, 
            0
        );
    }
    return array_sum($m);
}

Really nice solution!

what's the runtime? it's not quite clear how many times this walks bath and forth down the array, but it's definitely not linear.