Maximize sum of weights with constraints given on left and right indices in array

Question

I recently came through an interesting coding problem, which is as follows:

There are n boxes, let us assume this is an array of n boxes.

For each index i of this array, three values are given -

1.) Weight(i)

2.) Left(i)

3.) Right(i)

left(i) means - if weight[i] is chosen, we are not allowed to choose left[i] elements from the left of this ith element.

Similarly, right[i] means if arr[i] is chosen, we are not allowed to choose right[i] elements from the right of it.

Example :

Weight[2] = 5

Left[2] = 1

Right[2] = 3

Then, if I pick element at position 2, I get weight of 5 units. But, I cannot pick elements at position {1} (due to left constraint). And cannot pick elements at position {3,4,5} (due to right constraint).

Objective - We need to calculate the maximum sum of the weights we can pick.

Sample Test Case :-

**Input: **

5

2 0 3

4 0 0

3 2 0

7 2 1

9 2 0

**Output: **

13

Note - First column is weights, Second column is left constraints, Third column is right constraints

I used Dynamic Programming approach(similar to Longest Increasing Subsequence) to reach a O(n^2) solution. But, not able to think of a O(n*logn) solution. (n can be up to 10^5.)

I also tried to use priority queue, in which elements with lower value of (right[i] + i) are given higher priority(assigned higher priority to element with lower value of "i", in case primary key value is equal). But, it is also giving timeout error.

Any other approach for this? or any optimization in priority queue method? I can post both of my codes if needed. Thanks.

Answer 1

One approach is to use a binary indexed tree to create a data structure that makes it easy to do two operations in O(logn) time each:

1. Insert number into an array
2. Find maximum in a given range

We will use this data structure to hold the maximum weight that can be achieved by selecting box i along with an optimal selection of boxes to the left.

The key is that we will only insert values into this data structure when we reach a point where the right constraint has been met.

To find the best value for box i, we need to find the maximum value in the data structure for all points up to location i-left[i], which can be done in O(logn).

The final algorithm is to loop over i=0..n-1 and for each i:

1. Compute result for box i by finding maximum in range 0..(i-left[i])
2. Schedule the result to be added when we reach location i+right[i]
3. Add any previously scheduled results into our data structure

The final result is the maximum value in the whole data structure.

Overall, the complexity is o(nlogn) because each value of i results in one lookup and one update operation.