double largestSumOfAverages(vector<int>& A, int K) {
        vector<vector<double>> memo(K + 1, vector<double>(A.size(), numeric_limits<int>::min()));

        for (int k = 1; k <= K; ++k) {
            for (int l = 0; l < A.size(); ++l) { // k-th segment left
                double curr_sum = 0;
                for (int r = l; r < A.size(); ++r) { // k-th segment right
                    curr_sum += A[r];
                    double curr_avg = curr_sum / (r - l + 1);
                    double k_1_avg = l > 0 ? memo[k - 1][l - 1] : 0;
                    memo[k][r] = max(memo[k][r], k_1_avg + curr_avg);
                }
            }
        }

        return memo.back().back();
    }