Здравствуйте,
Есть интересная задача, нужен совет в разработке алгоритма решения.
Задача: Есть массив состоящий из n элементов. Определить минимальное количество элементов которые можно выкинуть при котором массив станет возрастающим.
Вот как я делал:
Решение:
Пусть в переменной $k содержится минимальное количество элементов которые нужно выкинуть.
1 шаг. Убираем слева элементы по условию Если $a[0]>$a[1], то убираем $a[0]; $k++; сдвигаем массив влево.
2 шаг. Убираем справа элементы по условию Если $a[$n-2]>$a[$n-1], то убираем $a[$n-1]; $k++;
3 шаг. Ищем лишние элементы в середине массива по условию "Если ($a[$i-1] > $a[$i]) and ($a[$i]>a[$i+1]), то выкидываем $a[$i]; $k++; сдвигаем массив влево.
4 шаг. После всех удалённых (лишних элементов) получаем массив, где последовательно идут (1, 2, 3 ...) массивов. Пример $a=array(4, 6, 2, 5, 8); => (4, 6) и (2, 5, 8); Определяем самый длинный из массивов упорядоченных по возрастанию и записываем его длину в $t.
$k=$k+(count($a)-$t);

Вроде б всё работало как надо, а тут ввёл массив (1, 3, 2, 5, 8) и ответ получился = 2, хотя достаточно выкинуть только 3, чтобы массив стал возрастающим.
Если есть идеи как доработать алгоритм или есть какой-то другой жажду услышать!

если правильно понял, то

function bCount(array $array = array())
        {
            $r = 0;
            $array = array_values($array);
            for ($i = 0, $c = count($array) - 1; $i < $c; $i++) {

                if ($array[$i + 1] <= $array[$i]) {

                    $array[$i + 1] = $array[$i];
                    ++$r;
                }
            }
            return $r;
        }

проверил работу функции (не всё так просто) :)

echo bCount(array(3, 1, 2, 5, 8)); 

выдаёт 2, хотя достаточно убрать только 3 из начала

а при

echo bCount(array(1, 3, 2, 5, 8)); 

действительно 1 выдаёт

Действительно баг, вот еще вариант :)

function bCount(array $array = array())
{
    $r = 0;
    $array = array_values($array);
    for ($i = 0, $c = count($array) - 1; $i < $c; $i++) {

        if ($array[$i + 1] <= $array[$i]) {

            $array[$i + 1] = $array[$i] < $array[$i + 1] ? $array[$i] : $array[$i + 1];
            ++$r;
        }
    }
    return $r;
}

echo bCount(array(1, 2, 3, 1, 2 ,3, 4));

выдаёт 1, хотя минимальное количество элементов которые над убрать = 2 (2, 3) из начала :)
и получится (1, 1, 2, 3, 4)

(1, 1, 2, 3, 4) - это не возрастающая последовательность, нужно убрать три элемента. Последняя попытка, если опять не угадал, то сдаюсь (уже спать пора ))

function bCount(array $array = array())
{
    $r = 0;
    $array = array_values($array);

    for ($i = 0, $c = count($array) - 1; $i < $c; $i++) {

        if ($array[$i + 1] <= $array[$i]) {

            if ($i != 0) {

                $array[$i + 1] = $array[$i];
            }
            ++$r;
        }
    }
    return $r;
}

echo bCount(array(1, 2, 3, 4, 9, 5, 6, 7, 8, 9));

выдаёт 5, хотя нужно убрать ток один элемент (9)

отпустите меня пожалуйста, я хочу спать и уже скоро на работу ))))

        function bCount(array $array = array())
        {
            $r = 0;
            $array = array_values($array);

            for ($i = 0, $c = count($array) - 1; $i < $c; $i++) {

                if ($array[$i + 1] <= $array[$i]) {

                    if ($i != 0) {

                        unset($array[$i]);
                        $array = array_values($array);
                        $c = count($array) - 1;
                        $i = $i - 2;
                    }
                    ++$r;
                }
            }
            return $r;
        }

echo bCount(array(2, 3, 1));

выдаёт 2
:D тут лучше не увлекаться, а то работу проспите