You have an array with n elements. The elements are either 0 or 1. You want to split the array into kcontiguous subarrays. The size of each subarray can vary between ceil(n/2k) and floor(3n/2k). You can assume that k << n. After you split the array into k subarrays. One element of each subarray will be randomly selected.

Devise an algorithm for maximizing the sum of the randomly selected elements from the k subarrays. Basically means that we will want to split the array in such way such that the sum of all the expected values for the elements selected from each subarray is maximum.

You can assume that n is a power of 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

Source -> http://stackoverflow.com/questions/8189334/google-combinatorial-optimization-interview-problm

### Like this:

Like Loading...

*Related*