Задача на собеседовании по комбинаторной оптимизации Google

Мне задали этот вопрос на интервью для Google пару недель назад, я не совсем понял ответа, и мне было интересно, может ли кто-нибудь здесь мне помочь.

У вас есть массив из n элементов. Элементы равны 0 или 1. Вы хотите разбить массив на k смежных подмассивов . Размер каждого подмассива может варьироваться от ceil (n / 2k) до floor (3n / 2k). Вы можете предположить, что k << n. После того, как вы разбили массив на k подмассивов. Случайным образом будет выбран один элемент каждого подмассива.

Разработайте алгоритм для максимизации суммы случайно выбранных элементов из k подмассивов. В основном означает, что мы захотим разбить массив таким образом, чтобы сумма всех ожидаемых значений для элементов выбирается из каждого подмассива.

Вы можете предположить, что n - степень двойки.

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