ผลรวมค่าเฉลี่ยสูงสุดของการแบ่งกลุ่ม (Largest Sum of Averages) ใน C++

แบ่งอาร์เรย์ A เป็นสูงสุด K กลุ่มติดกัน คะแนน = ผลรวมค่าเฉลี่ยแต่ละกลุ่ม หาคะแนนสูงสุด

ตัวอย่าง

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

คำอธิบาย − แบ่ง: [9], [1,2,3], [9] → 9 + (6/3) + 9 = 20

แนวทางการแก้ปัญหา (DP + Memoization)

• dp[i][k] = คะแนนสูงสุดจากตำแหน่ง i ด้วย k กลุ่มที่เหลือ
• ลองจบกลุ่มที่ j (i ≤ j < n): ค่าเฉลี่ย i..j + dp[j+1][k-1]
• ใช้ prefix sum คำนวณค่าเฉลี่ย O(1)
• Base: i ≥ n → 0, k = 0 → -inf

ตัวอย่างโค้ด C++

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

class Solution {
    vector> dp;
    vector A;
    int n;
    
    double solve(int idx, int k) {
        if (idx >= n) return 0;
        if (k == 0) return -1e9;
        if (dp[idx][k] >= 0) return dp[idx][k];
        
        double best = -1e9, sum = 0;
        for (int i = idx; i < n; i++) {
            sum += A[i];
            double avg = sum / (i - idx + 1);
            best = max(best, avg + solve(i + 1, k - 1));
        }
        return dp[idx][k] = best;
    }
public:
    double largestSumOfAverages(vector& A, int K) {
        this->A = A;
        n = A.size();
        dp.assign(n, vector(K + 1, -1));
        return solve(0, K);
    }
};

int main() {
    vector A = {9,1,2,3,9};
    Solution ob;
    cout << fixed << setprecision(1) << ob.largestSumOfAverages(A, 3); // 20.0
    return 0;
}

ผลลัพธ์

20