几周前,我在谷歌的一次采访中被问到这个问题,我没有得到答案,我想知道这里是否有人可以帮助我.
你有一个包含n个元素的数组.元素为0或1.您希望将数组拆分为k 个连续的子数组.每个子阵列的大小可以在ceil(n/2k)和floor(3n/2k)之间变化.你可以假设k << n.将数组拆分为k个子数组后.将随机选择每个子阵列的一个元素.
设计一种算法,用于最大化k个子阵列中随机选择的元素的总和.基本上意味着我们希望以这样的方式分割数组,使得从每个子阵列中选择的元素的所有期望值的总和最大.
你可以假设n是2的幂.
Example:
Array: [0,0,1,1,0,0,1,1,0,1,1,0]
n = 12
k = 3
Size of subarrays can be: 2,3,4,5,6
Possible subarrays [0,0,1] [1,0,0,1] [1,0,1,1,0]
Expected Value of the sum of the elements randomly selected from the subarrays: 1/3 + 2/4 + 3/5 = 43/30 ~ 1.4333333
Optimal split: [0,0,1,1,0,0][1,1][0,1,1,0]
Expected value of optimal split: 1/3 + 1 + 1/2 = 11/6 ~ 1.83333333