Tổng trung bình lớn nhất phân vùng mảng C++ (Largest Sum of Averages)

Phân chia mảng A thành tối đa K nhóm liền kề. Score = tổng trung bình cộng của từng nhóm. Tìm score lớn nhất.

Ví dụ

Input - A=[9,1,2,3,9], K=3 Output - 20

Giải thích - Phân chia: [9], [1,2,3], [9] → 9 + 6/3 + 9 = 20.

Phương pháp tiếp cận (DP + Memoization)

• dp[idx][k] = max score từ vị trí idx với k nhóm còn lại
• Đệ quy: thử mọi điểm cắt i từ idx đến n-1, score = avg(idx..i) + solve(i+1, k-1)
• Base case: idx ≥ n → 0; k=0 → -inf

Ví dụ code C++

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

class Solution {
public:
    vector<vector<double>> dp;

    double solve(vector<int>& A, int idx, int k) {
        if (idx >= A.size()) return 0;
        if (!k) return -100000;
        if (dp[idx][k] != -1) return dp[idx][k];

        double ret = INT_MIN, sum = 0;
        for (int i = idx; i < A.size(); i++) {
            sum += A[i];
            ret = max(ret, sum / (i - idx + 1) + solve(A, i + 1, k - 1));
        }
        return dp[idx][k] = ret;
    }

    double largestSumOfAverages(vector<int>& A, int K) {
        int n = A.size();
        dp.assign(n, vector<double>(K + 1, -1));
        return solve(A, 0, K);
    }
};

int main() {
    vector<int> v = {9, 1, 2, 3, 9};
    Solution ob;
    cout << ob.largestSumOfAverages(v, 3);
    return 0;
}

Kết quả

20