最近面了Oracle，有一题始终想不明白，希望各位大佬帮忙分析一下

波风水门 发表于 2019-11-23 22:25
反例：array=[2,2,3,3]，k=2

结果多少报一下？
2 | 2 3 3 = 8
3 | 2 2 3 = 7
2 2 | 3 3 = 6
2 3 | 2 3 = 5

5

337845818 发表于 2019-11-24 00:38
结果多少报一下？
2 | 2 3 3 = 8
3 | 2 2 3 = 7

他的做法不是 sort 之后再二分答案吗？你是基于什么操作交换 2 和 3 的位置的？

有一个想法不知可不可行, 从floor(total_sum/k)起,寻找有没有合适的组合刚好满足条件(sum of subset=floor(total_sum/k,其他的组合能组成k-1个subset,且和更小).如果找不到,则算floor(total_sum/k)+1, floor(total_sum/k)+2等等

ytsr 发表于 2019-11-23 14:26
step 1 取2个最大： 7 / 5
step 2 取下一个加到sum最小的组:   7 / 5 5
step 3 取下一个加到sum最小的 ...

根据楼主描述
Let us say we have array[]={1,2,3} and k=2;
then the possible subsets are[{1},{2,3}],[{2},{1,3}],[{3},{1,2}];
here the maximum sum in 1st case i.e in[{1},{2,3}] is 5.
Similarly for 2nd case it is 4 ,in 3rd case it is 3 ,Now the minimum among all these is 3.

层主这种分法的答案是13吧？

另一种分法是{5,4,3} {7, 5} 答案是12

我猜其实是leetcode 410 楼主听错了题 把subarray听成了subset?

TreeSet 发表于 2019-11-24 14:49
我猜其实是leetcode 410 楼主听错了题 把subarray听成了subset?

其实这题当时我还尝试用410的做法来做，但是面试官说子数组里的元素可以是不连续的，然后我就自闭了。。

波风水门 发表于 2019-11-24 00:50
他的做法不是 sort 之后再二分答案吗？你是基于什么操作交换 2 和 3 的位置的？

不考虑什么二分做法， 就是根据题意， 问你说的这个题的答案是多少？
最朴素的做法， 你算出来这题答案是什么？

337845818 发表于 2019-11-24 21:27
不考虑什么二分做法， 就是根据题意， 问你说的这个题的答案是多少？
最朴素的做法， 你算出来这题答案 ...

5 吧。。。
话说你是 wisdompeak 群里的嘛，我们回群里讨论吧，这里也太麻烦了。。。

如果没理解错的话， find the maximum sum of these subsets是要找到允许的最多的element的sum. 这里还要考虑里面有负数的可能。我的想法是首先sort，然后 sum (k for k in array[k - 1: ] if k > 0).

这题leetcode上有原题吗？


[微软]（北京上海苏州无锡）大量职位招人，长期提供内推
https://www.1point3acres.com/bbs/thread-555295-1-1.html