ค่าเฉลี่ยสูงสุดของการแบ่ง Partition อาร์เรย์ใน C++

โจทย์

ได้รับอาร์เรย์ เราแบ่งแถวของตัวเลข A เป็นกลุ่มติดกันสูงสุด K กลุ่ม (ไม่ว่าง) แล้วคะแนนคือผลรวมของค่าเฉลี่ยของแต่ละกลุ่ม คะแนนสูงสุดที่ทำได้คือเท่าไหร่?

ตัวอย่าง

ถ้าอินพุตอาร์เรย์คือ {9, 2, 5, 3, 10} สามารถแบ่งได้ดังนี้

{9} {2, 5, 3} และ {10} แล้วผลรวมค่าเฉลี่ยคือ

9 + (2 + 5 + 3) / 3 + 10 = 22.33

อัลกอริทึม

ใช้เทคนิค Memoization เพื่อแก้ปัญหานี้

• ให้ memo[i][k] เป็นคะแนนดีที่สุดเมื่อแบ่ง A[i ถึง n-1] เป็นสูงสุด K ส่วน
• ในกลุ่มแรก เราแบ่ง A[i ถึง n-1] เป็น A[i ถึง j-1] และ A[j ถึง n-1] แล้วคะแนนโคแดดิเดทคือ average(i, j) + score(j, k-1) โดย average(i, j) = (A[i] + ... + A[j-1]) / (j - i) เราเลือกคะแนนสูงสุด
• โดยรวม Recursion คือ: memo[n][k] = max(memo[n][k], score(memo, i, A, k-1) + average(i, j))

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

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

#define MAX 1000
double memo[MAX][MAX];

double score(int n, vector<int>& arr, int k) {
    if (memo[n][k] > 0) {
        return memo[n][k];
    }
    double sum = 0;
    for (int i = n - 1; i > 0; i--) {
        sum += arr[i];
        memo[n][k] = max(memo[n][k], score(i, arr, k - 1) + sum / (n - i));
    }
    return memo[n][k];
}

double getLargestSum(vector<int>& arr, int K) {
    int n = arr.size();
    double sum = 0;
    memset(memo, 0.0, sizeof(memo));
    for (int i = 0; i < n; i++) {
        sum += arr[i];
        memo[i + 1][1] = sum / (i + 1);
    }
    return score(n, arr, K);
}

int main() {
    vector<int> arr = {9, 2, 5, 3, 10};
    int K = 3;
    cout << "Largest sum = " << getLargestSum(arr, K) << endl;
    return 0;
}

ผลลัพธ์

Largest sum = 22.3333