題目網址：https://leetcode.cn/problems/largest-sum-of-averages/

題意：給一 array nums 和一整數 k, 將 nums 分成最多 k 個相鄰的非空 subarray。分數為每個 subarray 內的平均值之總和。

注意：必須使用 nums 中的每一個數進行分組, 且分數不一定是整數。

返回所能得到的最大分數, 答案誤差在 $10^{-6}$ 內都會被視為是正確的。

Solution：

想法：利用 DP

1. 定義狀態：

  • 首先, 會在 nums 前先加上一個 0, 代表什麼元素都沒有的狀態
  • dp[i][k]：nums[1:i] 分成 k 個 group 的平均值之最大總和

2. 得到轉移方程：

  • dp[i][k] = max(dp[i][k], dp[j - 1][k - 1] + sum / (i - j + 1));, 其中 1 ≤ j ≤ i
  • 最後一個元素 nums[i], 必定是在當前最後一個連續 subarray 中, 因此要考慮這個區間的起始元素 j 會在哪裡 ➔ 故從 i 往前倒推

3. 初始化：

  • dp[0][0]：空 array 分成 0 個 group 之最大平均值之總和為 0
    ➔ dp[0][0] = 0
  • dp[i][0]：非空 array 不可能分成 0 個 group, 故用 INT_MIN / 2 代表不可能。由於題目要求最大值, 故初始值要設小, 但設 INT_MIN 後續計算會 overflow, 故設 INT_MIN / 2
    ➔ dp[i][0] = INT_MIN / 2, 其中 1 ≤ i ≤ n
  • dp[0][k]：空 array 不可能分成 k 個 group, 故用 INT_MIN / 2 代表不可能
    ➔ dp[0][k] = INT_MIN / 2, 其中 1 ≤ k ≤ k_
class Solution {
public:
    double largestSumOfAverages(vector<int>& nums, int k) {
        const int n = nums.size();
        int k_ = k;
        vector<vector<double>> dp(n + 1, vector<double>(k + 1, INT_MIN / 2));

        nums.emplace(nums.begin(), 0);
        dp[0][0] = 0;

        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k <= min(i, k_); ++k) {
                double sum = 0; // 計算最後一個區間之平均
                for (int j = i; j >= k; --j) { // 從最後一個元素 i 往前倒推
                    sum += nums[j];
                    dp[i][k] = max(dp[i][k], dp[j - 1][k - 1] + sum / (i - j + 1));
                }
            }
        }

        return dp[n][k];
    }
};
  • time：$O(n^2 \cdot k)$ ➔ for loop 中 i、k、j 所需的時間分別為 $O(n)$、$O(k)$、$O(n)$
  • space：$O(n \cdot k)$ ➔ dp