Задача: 1043. Partition Array for Maximum Sum
Сложность: medium

Если задан целочисленный массив arr, разбейте его на (смежные) подмассивы длины не более k. После разбиения значения каждого подмассива меняются так, чтобы стать максимальным значением этого подмассива. Верните наибольшую сумму заданного массива после разбиения. Тестовые примеры генерируются таким образом, чтобы ответ умещался в 32-битное целое число.

Пример:

Input: arr = [1,15,7,9,2,5,10], k = 3
Output: 84

👨‍💻 Алгоритм:

1⃣Инициализация:
Создаем массив dp, где dp[i] будет хранить наибольшую сумму подмассива, заканчивающегося в позиции i.

2⃣Заполнение массива dp:
Проходим по массиву arr и для каждой позиции i пытаемся разбить подмассив длины до k и обновить dp[i] с максимальной возможной суммой.

3⃣Поддержание максимального значения в подмассиве:
Для каждого подмассива длины 1 до k, вычисляем максимальное значение в этом подмассиве и обновляем dp[i].

😎 Решение:

function maxSumAfterPartitioning($arr, $k) {
    $n = count($arr);
    $dp = array_fill(0, $n, 0);
    
    for ($i = 0; $i < $n; $i++) {
        $maxVal = 0;
        for ($j = 1; $j <= $k; $j++) {
            if ($i - $j + 1 >= 0) {
                $maxVal = max($maxVal, $arr[$i - $j + 1]);
                if ($i - $j >= 0) {
                    $dp[$i] = max($dp[$i], $dp[$i - $j] + $maxVal * $j);
                } else {
                    $dp[$i] = max($dp[$i], $maxVal * $j);
                }
            }
        }
    }
    
    return $dp[$n - 1];
}

Ставь 👍 и забирай 📚 Базу знаний