# 0813. Largest Sum of Averages
###### tags: `Leetcode` `Medium` `Dynamic Programming`
Link: https://leetcode.com/problems/largest-sum-of-averages/
## 思路
要注意dp初始值的定义
区间型I要注意```dp[i][0]```和```dp[0][0]```
由于要求max ```dp[i][0]```又不合法 我们要给它一个值 使得它永远不会被选到
这时候会想到用```Double.MIN_VALUE``` 但是它的值其实是0 所以应该用```Integer.MIN_VALUE/2```
## Code

class Solution {
    public double largestSumOfAverages(int[] nums, int k) {
        int n = nums.length;
        int[] arr = new int[n+1];
        for(int i=0; i<n; i++) arr[i+1] = nums[i];
        double[][] avgDP = new double[n+1][n+1];
        for(int i=1; i<=n; i++){
            for(int j=i; j<=n; j++){
                if(i==j) avgDP[i][j] = arr[i];
                else avgDP[i][j] = (avgDP[i][j-1]*(j-i)+arr[j])/(j-i+1);
            }
        }
        
        double[][] dp = new double[n+1][n+1];
        for(int i=1; i<=n; i++) dp[i][0] = Integer.MIN_VALUE/2;
        for(int i=1; i<=n; i++){
            for(int tempk=1; tempk<=Math.min(k, i); tempk++){
                for(int j=i; j>=tempk; j--){
                    dp[i][tempk] = Math.max(dp[i][tempk], dp[j-1][tempk-1]+avgDP[j][i]);
                }
            }
        }
        
        double ans = 0;
        for(int i=1; i<=k; i++) ans = Math.max(ans, dp[n][i]);
        return ans;
    }
}