[LeetCode]Largest Sum of Averages

标准的DP题目，我们用DP[k][i]表示前i个元素分成k个区间的最大average sum。我们可以推得递推公式：

• dp[k][i] = max(dp[k - 1][j] + average(j, i)), where k - 1 <= j <= i

假设数组长度为n，时间复杂度O(nk * n ^ 2)，空间复杂度O(n * k)，代码如下：

我们可以用滚动数组把空间优化到O(n)，代码如下：