Вадим

Попробуйте i > left. Иначе у вас при i=0 получается доступ к не существующему элементу a[-1]

Максим не пробовали смотреть в сторону шаблона проектирования стратегия? Каждое поведение - определённая стратегия, описанная классом. За создание колобков будет отвечать фабрика, которая на вход принимает характер и использует маппер для получения необходимых стратегий поведения по характеру.
Сами стратегии можно комбинировать между собой используя паттерн проектирования декоратор.

kolomiec_artiom Добавляя к своим комментариям, позволил себе написать алгоритм. Он схож с вашим, но есть некоторые отличия о которых я писал в комментариях.

Вывод алгоритма (данные внутри кода)

php solution.php
Steps: 1 2 4 6 9
Values: 10 20 30 -100 100000

Сам алгоритм:

<?php

$k = 3;
$weight = [1 => 10, 20, -5, 30, -5, -100, -3000, -5000, 100000];
$n = count($weight);

$sum = [];
$comeFrom = [];

$sum[0] = 0;
$comeFrom[0] = 0;

for ($i = 1; $i <= $n; $i++) {
    $comeFromIndex = $i - 1;
    for ($j = max(0, $i - $k); $j <= ($i - 1); $j++) {
        if ($sum[$j] > $sum[$comeFromIndex]) {
            $comeFromIndex = $j;
        }
    }

    $sum[$i] = $sum[$comeFromIndex] + $weight[$i];
    $comeFrom[$i] = $comeFromIndex;
}

$steps = [];
while ($n) {
    $steps[] = $n;
    $n = $comeFrom[$n];
}

echo 'Steps: ' . implode(' ', array_reverse($steps));
echo "\n";
echo 'Values: ' . implode(' ', array_intersect_key($weight, array_combine($steps, $steps)));