1004. Largest Sum of Averages 和1251. Split Array Largest Sum思路一样

class Solution {
public:
    /**
     * @param A: an array
     * @param K: an integer
     * @return: the largest score
     */
    double largestSumOfAverages(vector<int> &A, int K) {
        // Write your code here
        //DP 
        const int size = A.size();
        if(size == 0){
            return 0; 
        }
        vector<double> prefixSum(size + 1, 0); 
        for(int i = 1; i <= size; i++){
            prefixSum[i] = prefixSum[i - 1] + A[i - 1]; 
        }
        if(K >= size){
            return prefixSum[size]; 
        }
        if(K == 1){
            return prefixSum[size] / size; 
        }
        
        vector<vector<double>> dp(K + 1, vector<double>(size + 1)); 

        for(int i = 1; i <= size; i++){
            dp[1][i] = prefixSum[i] / i; 
        }
        for(int i = 2; i <= K; i++){
            for(int j = i; j <= size; j++){
                for(int k = i - 1; k < j; k++){
                    double val = dp[i-1][k] + (prefixSum[j] - prefixSum[k])/(j - k); 
                    dp[i][j] = max(dp[i][j], val); 
                }
            }
        }
        return dp[K][size]; 
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41