813. Largest Sum of Averages

leetcode

#array#bit-manipulation#csharp#dynamic-programming#leetcode#math#prefix-sum#recursion

Task

: medium

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

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

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

Пример:

Input: nums = [9,1,2,3,9], k = 3

Output: 20.00000

Explanation:

The best choice is to partition nums into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.

We could have also partitioned nums into [9, 1], [2], [3, 9], for example.

That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.

C# solution

matched/original

using System;
public class Solution {
    public double LargestSumOfAverages(int[] A, int K) {
        int N = A.Length;
        double[] P = new double[N + 1];
        // Префиксные суммы
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];
        double[] dp = new double[N];
       
        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] = Math.Max(dp[i], (P[j] - P[i]) / (j - i) + dp[j]);
                }
            }
        }
        return dp[0];
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public double LargestSumOfAverages(vector<int>& A, int K) {
        int N = A.size();
        double[] P = new double[N + 1];
        // Префиксные суммы
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];
        double[] dp = new double[N];
       
        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];
    }
}

Java solution

matched/original

class Solution {
    public double largestSumOfAverages(int[] A, int K) {
        int N = A.length;
        double[] P = new double[N + 1];
        for (int i = 0; i < N; ++i)
            P[i + 1] = P[i] + A[i];
        
        double[][] dp = new double[N][N];
        for (int i = 0; i < N; ++i)
            dp[i][0] = (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][0] = Math.max(dp[i][0], (P[j] - P[i]) / (j - i) + dp[j][0]);
                }
            }
        }
        
        return dp[0][0];
    }

JavaScript solution

matched/original

var largestSumOfAverages = function(A, K) {
    const N = A.length;
    const P = new Array(N + 1).fill(0);
    for (let i = 0; i < N; i++) {
        P[i + 1] = P[i] + A[i];
    }
    
    const dp = new Array(N).fill(0);
    for (let i = 0; i < N; i++) {
        dp[i] = (P[N] - P[i]) / (N - i);
    }
    
    for (let k = 0; k < K - 1; k++) {
        for (let i = 0; i < N; i++) {
            for (let j = i + 1; j < N; j++) {
                dp[i] = Math.max(dp[i], (P[j] - P[i]) / (j - i) + dp[j]);
            }
        }
    }
    
    return dp[0];

Go solution

matched/original

func largestSumOfAverages(A []int, K int) float64 {
    N := len(A)
    P := make([]float64, N+1)
    for i := 0; i < N; i++ {
        P[i+1] = P[i] + float64(A[i])
    }
    
    dp := make([]float64, N)
    for i := 0; i < N; i++ {
        dp[i] = (P[N] - P[i]) / float64(N-i)
    }
    
    for k := 0; k < K-1; k++ {
        for i := 0; i < N; i++ {
            for j := i+1; j < N; j++ {
                dp[i] = max(dp[i], (P[j] - P[i]) / float64(j-i) + dp[j])
            }
        }
    }
    
    return dp[0]
}

func max(a, b float64) float64 {
    if a > b {
        return a
    }
    return b
}

Explanation

Algorithm

Пусть 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).

Наша реализация демонстрирует подход "снизу вверх" для динамического программирования. На шаге 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)).

😎