Finding higher values from arrays that are all closer than predefined distances

Question

I have arrays a₁ to a_n each containing m number of elements. I have another symmetric n X n matrix b containing distance between the arrays. I want to select one element from each array x₁ to x_n limited to the following constraint. (a₁ is an array and x₁ a single value taken from a₁)

1. For every x_i (which was originally a_iu) and x_j (which was originally a_jv), where i is not same as j, and u and v are the original array indices, we have |u - v| <= b_ij.
2. The total sum of x₁ to x_n is the maximum of all possible such sets.

An example

a1 = [1, 2, 3, 8, -1, -1, 0, -1]
a2 = [1, 2, 4, 0, -1, 1, 10, 11]

b  = |0, 2|
     |2, 0|

The selected values are x₁ = 8 and x₂ = 4. One can notice that we didn't select 10 or 11 from the second because the nearest possible value for any of them is just 0.

Now when I have only two arrays I can do the following in java in O(n²) time, I guess, and find the maximum sum, which is 12 in this case. How can I achieve better solution for more than 2 arrays?

int[][] a = new int[][]{{1, 2, 3, 8, -1, -1, 1, -1}, {1, 2, 4, 0, -1, 1, 10, 11}};
int[][] b = new int[][]{{0, 2}, {2, 0}};
int maxVal = Integer.MIN_VALUE;
for (int i = 0; i < a[0].length; i++) {
    for (int j = Math.max(i - b[0][1], 0); j < Math.min(a[1].length, i + b[0][1]); j++) {
        maxVal = Math.max(maxVal, a[0][i] + a[1][j]);
    }
}
System.out.println("The max val: "+maxVal);

Answer 1

You can't use dynamic programming here, because there is no optimal substructure: the b_1n entry can ruin a highly valuable path from x_1 to x_{n-1}. So it's probably hard to avoid exponential time in general. However, for a set of b_ij that do reasonably restrict the choices, there is a straightforward backtracking approach that should have reasonable performance:

1. At each step, a value has been selected from some of the a_i, but no choice has yet been made from the others. (The arrays selected need not be a prefix of the list, or even contiguous.)
2. If a choice has been made for every array, return (from this recursive call) the score obtained.
3. Consider, for each pair of a chosen array and a remaining array, the interval of indices available for selection in the latter given the restriction on distance from the choice made in the former.
4. Intersect these intervals for each remaining array. If any intersection is empty, reject this proposed set of choices and backtrack.
5. Otherwise, select the remaining array with the smallest set of choices available. Add each choice to the set of proposed choices and recurse. Return the best score found and the choice made to obtain it, if any, or reject and backtrack.

The identification of the most-constrained array is critical to performance: it constitutes a form of fuzzy belief propagation, efficiently pruning future choices incompatible with present choices necessitated by prior choices. Depending on the sort of input you expect, there might be value in doing further prioritization/pruning based on achievable scores.

My 35-line Python implementation, given a 10x10 random matrix of small integers and b_ij a constant 2, ran in a few seconds. b_ij=3 (which allows up to 7 of the 10 values for each pair of arrays!) took about a minute.