LargestSumOfAverages [source code]
public class LargestSumOfAverages {
static
/******************************************************************************/
class Solution {
public double largestSumOfAverages(int[] A, int K) {
int N = A.length;
int[] left_sum = new int[N];
left_sum[0] = A[0];
for (int i = 1; i < N; i++)
left_sum[i] = left_sum[i - 1] + A[i];
double[] right_avg = new double[N];
for (int i = 0; i < N; i++)
right_avg[i] = (double) (left_sum[N - 1] - (i == 0 ? 0 : left_sum[i - 1])) / (N - i);
double[][] dp = new double[K + 1][N];
for (int i = 0; i < N; i++)
dp[1][i] = right_avg[i];
for (int k = 2; k <= K; k++) {
for (int i = 0; i < N; i++) {
dp[k][i] = dp[k - 1][i];
for (int j = i + 1; j < N; j++) {
dp[k][i] = Math.max (dp[k][i],
dp[k - 1][j] + (double) (left_sum[j - 1] - (i == 0 ? 0 : left_sum[i - 1])) / (j - i));
}
}
}
return dp[K][0];
}
}
/******************************************************************************/
public static void main(String[] args) {
LargestSumOfAverages.Solution tester = new LargestSumOfAverages.Solution();
int[][] inputs = {
{9,1,2,3,9}, {3},
};
double[] answers = {
20.0,
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[] A = inputs[2 * i];
int K = inputs[2 * i + 1][0];
double ans = answers[i], output = tester.largestSumOfAverages (A, K);
System.out.printf ("%s and %d\n%s\n%f",
Printer.array (A), K, Printer.wrap (output + "", Math.abs (output - ans) < 1e-5 ? 92 : 91), ans
);
}
}
}
这个题目给了一个K, 相当于无端端多了一个维度, 这个是一个非常警惕的DP题目的信号; 2018-05-05 20:44:44 事实上, 这种额外增加的维度是number of maximum operations allowed的反而是最危险的DP, 之前看过的POJ3666, 还有股票交易问题, 都跟这个类型的DP维度有关系;
虽然有这个信号, 不过这个题目还是完全没有思路; 既然知道是DP题目, 那么之前有一个教训, 就是要多找可能性的path, 然后在当中通过人逻辑总结最优的过程来找到DP计算方式;
2018-05-05 20:45:39 隔了一段时间回来看, 这道题的upvote相当的高, 150/1, 这个是很少见的好评率了;
回过头来重新看这个题目, 还是怎么看怎么像一个经典的算法题目, 那种解法很成熟的题目; 就是想不到怎么做;
看完editorial之后理解这个题目自己尝试写一下; 暂时不考虑空间优化, 为了后面复习的时候看这个代码方便;
最后还是有惊无险的过了, 速度是26(NA). 在自己实现的过程当中, 还是有很多学到了的地方;
首先, 发现下面的awice的写法当中, 他一开始的P, 也就是sum数组, 之所以选择错位一个(P[i]的i代表的是prefix length而不是index), 还是有道理的, 看我自己上面写的代码就知道了, 查询这个sum数组的时候, 各种需要向前查询: 这个时候他错位的写法, 就导致在前面[0]位置加了一个类似sentinel的东西, 所以对i >= 0的判断就不需要了; 我上面的代码看起来就比他的啰嗦很多;
然后还有一个小技巧, 就是你看他这个sum的时候, 就用的一个double数组; 我没有想到这一点, sum用的是一个int数组, 最后导致在后半段的各种double计算的时候还要cast; 很麻烦;
然后最后返回的结果应该是[K-1][0], 而不是[K-1][N-1], 这个如果你理解了这个算法的本质, 就知道了, 我们是一个dp[i]代表的是i..N-1这个subproblem, 所以最后整个problem是0..N-1, 对应的DP左边是最左边的0而不是最右边;
另外一个小的东西, 就是看我, 实际上最后k只有K个值, 1..K, awice的写法也一样, 是0..K-1. 我一开始写的不对, 我一开始把dp[0][:]初始化为right_avg, 然后走一个k=1..K的循环, 这个就错了, 我初始化的时候给的是一个at most 1的结果, 然后后面又重新算了K次, 最后得到的是一个at most K+1的结果;
还是一句话, 要理解题目的道理, 而不是单纯的机械记忆: 看到给你个K, 就直接计算到K为止, 那就太傻了;
类似的, 以前学DP的时候其实也经常强调, 除了填表顺序, 初始化也非常重要;
另外, 这题其实不压缩空间维度的话, 代码写起来反而啰嗦, 你看我自己的循环写法, 每一个dp[k][i]还要先从dp[k-1][i]给取过来, 然后再扫j;
这里一开始还犯了一个错误, 写成了这样:
dp[k][i] = Math.max (dp[k - 1][i],
dp[k - 1][j] + (double) (left_sum[j - 1] - (i == 0 ? 0 : left_sum[i - 1])) / (j - i));
看起来很对, 不是吗? 但是max的第一项不应该是还看k-1的结果: 当前j左边的所有j可能已经更新过了dp[k][i], 然而你还是一直跟上一行的dp[k-1][i]比, 这个就有问题了; 所以正确的做法是一开始就让dp[k][i]copy dp[k-1, i], 然后, 在当前行进行一个max搜索; 因为i是从左向右, 所以在算dp[k][i]的时候, 所有当前i右边的[k, i+1:]都还没有计算, 所以对于这些位置, 去查询[k-1]还是[k]是无所谓的; 不对, 有所谓, 必须是[k-1]: 这个时候这些大i的[k]还没有初始化, 还是0;
总体来说这个算法还是很有意思的, 不自己实现一遍很多坑完全不知道;
UNFINISHED
editorial
Approach #1: Dynamic Programming [Accepted]
Intuition
The best score partitioning A[i:] into at most K parts depends on answers to paritioning A[j:] (j > i) into less parts. We can use dynamic programming as the states form a directed acyclic graph.
大概的分析还是很简单粗暴的: 并不是直接从题目出发, 分析题目观察到说应该用DP, 而是直接看到DP能做, 有Guoye口中的subsolution的性质, 就直接用;
另外这里这个acyclic, 对应的可能就是我自己理解的填表顺序. 有这样一个树状结构, 才能设计出来合理的填表顺序;
DP的两个维度就是比较直接的, 一个是长度(也就是problem的size), 一个就是explicit给出的这个maximum number of operations;
Algorithm
Let dp(i, k) be the best score partioning A[i:] into at most K parts.
定义很清晰;
If the first group we partition A[i:] into ends before j, then our candidate partition has score average(i, j) + dp(j, k-1)), where average(i, j) = (A[i] + A[i+1] + ... + A[j-1]) / (j - i) (floating point division). We take the highest score of these, keeping in mind we don't necessarily need to partition - dp(i, k) can also be just average(i, N).
跟LIS一样的DP思路: 每一个格子的填表都要把前面所有的subsolution都遍历一遍;
这里的这个dp decision有点类似背包问题里面, 第一个包装多少; 想想这个问题其实跟背包问题是有点类似的;
In total, our recursion in the general case is dp(i, k) = max(average(i, N), max_{j > i}(average(i, j) + dp(j, k-1))).
很明确的DP公式, 这个也是三分地里面一些面试官强调的, DP问题给出非常清晰的formula对于最后的打分非常重要;
We can calculate average a little bit faster by remembering prefix sums. If P[x+1] = A[0] + A[1] + ... + A[x], then average(i, j) = (P[j] - P[i]) / (j - i).
这个优化就跟滑动窗口算sum类信息一样的, 应该是我能想得到的: sliding window for aggregate类似的技巧;
另外他这个average(i,j)代表的应该是i..j-1段的average; 因为dp(j)代表的是j..段的; 下面的代码好像也是对应这个符号定义: 设计代码的时候这个符号定义就搞清楚是一个好事;
当然了, 开区间的定义方式, 我现在还没有十足的把握驾轻就熟, 所以我还是选择能用闭区间的还是用闭区间;
Our implementation showcases a "bottom-up" style of dp. Here at loop number k in our outer-most loop, dp[i] represents dp(i, k) from the discussion above, and we are calculating the next layer dp(i, k+1). The end of our second loop for i = 0..N-1 represents finishing the calculation of the correct value for dp(i, t), and the inner-most loop performs the calculation max_{j > i}(average(i, j) + dp(j, k)).
好像意思是填表的是for i for k这样的顺序, i是外层循环; 哦不对, 看下面代码, 实际上是for k for i的顺序;
class Solution {
public double largestSumOfAverages(int[] A, int K) {
int N = A.length;
double[] P = new double[N+1];
for (int i = 0; i < N; ++i)
P[i+1] = P[i] + A[i];
double[] dp = new double[N];
for (int i = 0; i < N; ++i)
dp[i] = (P[N] - P[i]) / (N - i);
for (int k = 0; k < K-1; ++k)
for (int i = 0; i < N; ++i)
for (int j = i+1; j < N; ++j)
dp[i] = Math.max(dp[i], (P[j]-P[i]) / (j-i) + dp[j]);
return dp[0];
}
}
你看他第一个循环, 这个好像是awice喜欢的循环的写法; 反正我不用管就行了; 知道i=0..N-1, 然后被P和A用来index, 然后i+1 = 1..N, 被左边的P用来index, 就没什么复杂的;
P计算的应该是一个sum; 具体, 脑子里不要空想, 就用一个比如N=3的例子来帮助理解, 看P到底算的是什么:
index:
0 1 2 // i
1 2 3 // i + 1
这个P的坐标有一个错位, 有点奇怪, P[i]算的好像是sum(A[0..i-1]). 我不赞成这个做法; 这个明显是一个坐标对应subproblem inclusive end的就行了, 没有必要像dot思路那样错位;
当然, 也可以用1based来解释这个错位: P[i]等于sum of the prefix of length i; 进一步, 也可以理解为P[i]是sum of all elements before A[i]: 借用index和length之间的关系;
average DP
dp的index范围是0..N-1, 所以是一个直接针对index的结果; 根据上面的解释, dp[i] = (P[N] - P[i]) / (N - i) 计算的应该就是i..N-1闭区间的average; i一直向后到头;
这个用sum来计算average DP数组的方法也要熟悉, 好像之前其实并没有正式碰到过这个小技巧的实现;
尤其是后面自己实现过了之后发现, 这里实际上是有一个向左的所有的sum来计算向右的average, 这个还是有点counter intuitive的;
注意看我红线的画法; 这里我默认一个index对应的一个entry就是一个格子(阴影部分), 所以在囊括i..N-1这个范围内的所有的格子的时候, 我的左边的线对其的是[i]的左边缘, 右边的红线对齐的是[N-1]的右边缘; 这些其实确实是很简单的东西, 不过时常提醒一下自己, 不要面试的时候蒙圈儿. 面试的时候能够快速准确的画出图示, 非常的重要; 不要画个数组范围都磨磨唧唧, 立刻就被面试官认为有问题了;
这个是这个DP计算的过程:
这个也是符合之前的定义, 留意这里average的计算范围右边端点是开区间;
首先, dp[i]对应的是i..N-1的average, 这个设计是没有问题的; 另外, 理解这个为什么是整个DP的初始化, 也需要一点想头;
顺带还是回过来思考一下, 计算P的是时候还是不需要的, 就用average(i..N-1) = sum(0..N-1) - sum(0..i-1), 这样计算的sum数组也是完全可以用的;
回到正题, DP的初始化是average(i..N-1), 这个是上面推理的时候说了的, 就是一点都不分的base case;
最后kij这个大循环里面, ij循环实际上是好理解的; 一个不太好理解的是, k循环: k根本没有出现在任何的循环代码里面; 当然, 你可以用类似之前2D DP转化为1D DP的时候的理解, 这个实际上就是一个按行填表的时候的空间优化.
这个理解是没问题的; 但是有没有什么直观的理解: 为什么ij循环这个过程重复K次, 就是我们最后要的结果: 对应分成K组, without k even appearing anywhere in the inner loop.
可以这样理解, 还是上面最后一个图: recursion不好理解的时候, 第一步, 永远是从初始化开始: 不要一开始就go inductive, 开始思考arbitrary i -> i+1这种的; 就从0->1这种先开始思考, 然后看合适, 再arbitrary;
一开始的时候, 我们的dp[i]其实是把i..N-1分成只有一组的情况, 这个上面说了; 然后第一个k循环, 我们对这个i, 扫描所有的右边的j; 你思考一下, 这个做的是什么工作? 实际上就是在做一个把目前只是作为一份的i..N-1段, 尝试性的分出第二组. 注意, 这个尝试未必成功, 尤其是对于后面k大了之后. 比如现在i..N-1就是, 算了, 换具体数字, 比如i是1, 我们要分1..9, N=10. 然后现在dp[1]记录的数字是对应于把1..9分成1..4 and 5..9的做法; 注意, 这个信息是implicit的, 并没有存在DP里面;
然后下一个k循环, 我们i站在1, j继续从2开始向右; 你注意一个问题, 加入j能够成功把1..9从两份变成三份, 一定是分的1..4这一块; j不可能在5..9段成功: 因为假如...这个分析还是有点乱了;
一开始1..9是一段, 然后我们i在1, 然后j从2开始走到9, 这个过程是把1..9变成两段的过程; 然后i在2, 然后我们想把2..9变成两段; 注意为什么j的初始值是i+1而不是i: 这个并不是那么trivial的: 因为在当前的k, 我们在i, 我们是希望给i..N-1再多加一段. 如果j从i开始, 就有可能包含了不加分段的情况;
加入1..9段, 我们找到, j=5的时候最好, 也就是1..9=1..4 + 5..9是最好的; 然后我们开始处理2..9, 注意这个过程是不受之前1..9的处理的影响的; 这也是i为什么要从左到右; 这个题的填表顺序的设计其实是有点tricky的; 假如在第二k循环, 我们i从右向左, 那么我们在找到把2..9分成两段的办法之后, 走到1..9, 这个时候假如, 最后决定了1..9 = 1..1 + 2..9, 这个时候实际上是把1..9分成了三段了, 那么把1..9分成两段的decision就被跳过了, 这个会导致最后的结果有问题, 是一个很subtle的bug;
从左到右, 2..9的分两段的办法不依赖于1..9分两段的办法, 但是1..9分两段的办法, 依赖于2..9分一段的办法(上一个k循环的结果); 当然, i的这个填表顺序跟j的填表顺序是对应的;
回过头来, 假如分两段的k循环刚刚结束, 这个时候我们dp[1]存放的是1..9 = 1..4 + 5..9的结果. 然后我们进入分三段的k循环, 继续站在1..9思考干什么; 那么假如两段变三段成功(是有可能不成功的, 这也是为什么题目给的要求是at most而不是exactly K). 那么新增加的这个分界点, 是在1..4还是5..9呢? 我感觉应该只可能在1..4? 因为假如比如j找到的是7, 那么我们就分成了1..4 + 5..6 + 7..9, 这个对吗? DP计算的时候实际上是一个averaeg(1..6) + dp7, 这个最后实际上找到的还是一个两段的分法; 假如这个7成功, 意思就是实际上1..9 = 1..6 + 7..9才是最好的两段分法, 这个就contradict上一个k循环的结果最佳的assumption了;
这个解释感觉还是有点乱;
有没有什么数学解释表达不可能把1..4 + 5..9的第二段给拆分(在分三段的决策过程中)? 好像想不到;
所以这题真的是把k给消除掉之后, 给理解造成了很大的困难. 真正面试的时候, 我还是觉得, 对于DP问题, 空间优化不要急着去做;
这些理解完了, 这个算法应该就没问题了;
search return the result for n first numbers to k groups.
It's top-down solution and it keeps all process to memory.
So it's like a DP solution while DP is bottom-up.
I took suggestion from @MonnaGotIt and added a prunting: if (n < k) return 0;Time complexity: O(KN^2)
Java:
public double largestSumOfAverages(int[] A, int K) {
int N = A.length;
double[][] memo = new double[N+1][N+1];
double cur = 0;
for (int i = 0; i < N; ++i) {
cur += A[i];
memo[i + 1][1] = cur / (i + 1);
}
return search(N, K, A, memo);
}
public double search(int n, int k, int[] A, double[][] memo) {
if (memo[n][k] > 0) return memo[n][k];
if (n < k) return 0;
double cur = 0;
for (int i = n - 1; i > 0; --i) {
cur += A[i];
memo[n][k] = Math.max(memo[n][k], search(i, k - 1, A, memo) + cur / (n - i));
}
return memo[n][k];
}
还有其他语言的版本, 懒得抄了;
速度非常快, 只有13, 为什么啊; 我DP的写法居然还没有他这个快? 大家复杂度都是一样的啊;
另外, 上面那个DP其实还是可以进一步优化的: 分1..9 = 1..4 + 5..9的时候, 上面讨论了, 其实只要扫到1..4就行了, 所以如果把这个left most boundary这样的信息记录下来, 是可以进一步优化速度的; 对于复杂度分析可能没什么帮助, 实际速度应该很有帮助;
实现应该也不难, 就是额外记录一个表格就行了; 类似max操作的backpointer;
他这个average的计算还是比较简单的; 没有太多滑头的地方; 维护一个额外的sum so far, 让计算稍微更容易理解一些;
看他recursion, 参数表怎么变化, 来理解参数的含义; 只有n和k有变化, 那么就跟DP填表实际上应该是差不多的; memo就是这个表格;
base case最后看; 先看中心逻辑;
好像他主函数里面这个cur循环就是为了初始化memo而已;
在recursion里面, 每一个iteration他最后实际上还是重新用cur计算了一边average; 也就是他认为average本身的预处理是没有必要的;
另外, 看他的解释, 他有一个将n和k进行对比造成的pruning, 这个原理是好理解的, 这里也暴露了awice的做法的一个毛病: k完全不参与搜索过程; 这里可以看到, k是有必要参与的;
当然, 如果加上我自己上面描述的closest boundary pointer的优化, 我感觉他这个n<k的优化应该是能被涵盖的;
看了一下, search里面的cur从n开始计算的, 这个实际上跟awice写法是一样的; 整个算法最大的区别就是一个, 他这里是从右向左做的, 这个感觉应该没有太大差别吧;
二来, 他加了一个n < k的pruning; 删了这个优化之后是14, 还是很快;
awice的原版代码我提交了一下, 21, 所以应该主要不是我自己的实现的锅. 这个recursion写法看来就是有点更优秀的地方; 不懂是哪里;
TODO: 评论没有仔细看;
uwi:
class Solution {
public double largestSumOfAverages(int[] A, int K) {
int n = A.length;
double[] dp = new double[n+1];
Arrays.fill(dp, Double.NEGATIVE_INFINITY);
dp[0] = 0;
double ret = 0;
for(int i = 0;i < K;i++){
double[] ndp = new double[n+1];
Arrays.fill(ndp, Double.NEGATIVE_INFINITY);
for(int j = 0;j < n;j++){
double s = 0;
for(int k = j;k < n;k++){
s += A[k];
ndp[k+1] = Math.max(ndp[k+1], dp[j] + s/(k-j+1));
}
}
ret = Math.max(ret, ndp[n]);
dp = ndp;
}
return ret;
}
}
没仔细看, 好像是差不多的做法, 没有提前计算average查询数组; 这个不是很提倡. 我还是喜欢这种步骤分明的思考方式;
cchao:
double dp[110][110];
double sum[110];
class Solution {
public:
double largestSumOfAverages(vector<int>& a, int k) {
memset(dp, 0, sizeof dp);
const int n = a.size();
for (int i = 1; i < 110; ++i)
dp[0][i] = dp[i][0] = -1e15;
double ans = 0;
for (int i = 1; i <= n; ++i)
sum[i] = sum[i - 1] + a[i - 1];
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
dp[i][j] = -1e15;
for (int s = 1; s <= i; ++s) {
dp[i][j] = max(dp[i][j], dp[s - 1][j - 1] + double(sum[i] - sum[s - 1]) / (i - s + 1));
}
}
}
return dp[n][k];
}
};
没仔细看了, 看着像差不多;
Problem Description
We partition a row of numbers A into at most K adjacent (non-empty) groups, then our score is the sum of the average of each group. What is the largest score we can achieve?
Note that our partition must use every number in A, and that scores are not necessarily integers.
Example:
Input:
A = [9,1,2,3,9]
K = 3
Output: 20
Explanation:
The best choice is to partition A into [9], [1, 2, 3], [9]. The answer is 9 + (1 + 2 + 3) / 3 + 9 = 20.
We could have also partitioned A into [9, 1], [2], [3, 9], for example.
That partition would lead to a score of 5 + 2 + 6 = 13, which is worse.
Note:
- 1 <= A.length <= 100.
- 1 <= A[i] <= 10000.
- 1 <= K <= A.length.
- Answers within 10^-6 of the correct answer will be accepted as correct.
Difficulty:Medium
Total Accepted:421
Total Submissions:1.8K
Contributor:awice
Companies
google
Related Topics
dynamic programming