813. Наибольшая сумма средних значений (Largest Sum of Averages)

Задание.

Вам дается целочисленный массив nums и целое число k. Вы можете разбить массив не более чем на k непустых смежных подмассивов. Оценка раздела – это сумма средних значений каждого подмассива.

Обратите внимание, что в разделе должно использоваться каждое целое число в nums, и что оценка не обязательно является целым числом.

Верните максимальный балл, которого вы можете достичь из всех возможных разделов. Будут приняты ответы в пределах 10^-6 от фактического ответа.

Пример 1.

Входные данные: nums = [9,1,2,3,9], k = 3

Результат: 20.00000

Пояснение:

Лучший выбор -- разделить `nums` на [9], [1, 2, 3], [9]. Ответ таков 9 + (1 + 2 + 3) / 3 + 9 = 20.
Мы могли бы также разделить `nums` на [9, 1], [2], [3, 9], например.
Это разделение привело бы к множеству 5 + 2 + 6 = 13, что хуже.

Пример 2.

Входные данные: nums = [1,2,3,4,5,6,7], k = 4

Результат: 20.50000

Решение.

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int K) {

        int N = nums.size();
        vector<double> P(N+1, 0.);
        for (int i = 0; i < N; ++i) {
            P[i+1] = P[i] + nums[i];
        }

        vector<double> dp(N, 0.);
        for (int i = 0; i < N; ++i) {
            dp[i] = (P[N] - P[i]) / (N - i);
        }

        for (int k = 0; k < K-1; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = i+1; j < N; ++j) {
                    dp[i] = max(dp[i], (P[j]-P[i]) / (j-i) + dp[j]);
                }
            }
        }

        return dp[0];
    }
};

Способ решения #1. Динамическое программирование.

Интуиция

Лучший результат при разделении A[i:] не более чем на K частей зависит от ответов на вопрос о разделении A[j:] (j > i) на меньшее количество частей. Мы можем использовать динамическое программирование, поскольку состояния образуют ориентированный ациклический граф.

Алгоритм.

Пусть dp (i, k) – наилучший результат, разделяющий A[i:] не более чем на K частей.

Если первая группа, на которую мы разделяем A[i:], заканчивается перед j, то наш раздел-кандидат оценивается, как имеет average (i, j) + dp(j, k-1)), где average (i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (деление с плавающей запятой). Мы берем самый высокий балл из них, имея в виду, что нам не обязательно разделять - dp(i, k) также может быть просто average(i, N).

В целом, наша рекурсия в общем случае равна dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1)))

Запоминая префиксные суммы, можно рассчитывать average (среднее) чуть быстрее. Если P[x+1] = A[0] + A [1] + ... + A[x], то average(i, j) = (P[j] - P [i]) / (j - i).

Наша реализация демонстрирует стиль dp “снизу вверх”. Здесь, в цикле с номером k в нашем самом внешнем цикле, dp[i] представляет dp(i, k) из приведенного выше обсуждения, и мы вычисляем следующий уровень dp(i, k+1). Конец нашего второго цикла для i = 0..N-1 означает завершение вычисления правильного значения для dp(i, t), а самый внутренний цикл выполняет вычисление max_{j > i}(average(i, j) + dp(j, k)).

Реализация.

class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int K) {

        int N = nums.size();
        vector<double> P(N+1, 0.);
        for (int i = 0; i < N; ++i) {
            P[i+1] = P[i] + nums[i];
        }

        vector<double> dp(N, 0.);
        for (int i = 0; i < N; ++i) {
            dp[i] = (P[N] - P[i]) / (N - i);
        }

        for (int k = 0; k < K-1; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = i+1; j < N; ++j) {
                    dp[i] = max(dp[i], (P[j]-P[i]) / (j-i) + dp[j]);
                }
            }
        }

        return dp[0];
    }
};

Анализ сложности.

• По времени: O(K * N²), где N – размер nums

• По памяти: O(N), где N – размер dp.