I was working on a project and am stuck in the middle unable to find an optimal method to solve this problem. Consider an array $A$ of $n$ elements. I have to choose $k$ elements such that the sum of indices is maximal under the constraint of being less than a given element $x$. My approach for this is the naive $O(n^k)$ algorithm, but this would take a lot of time for large $n$.

This is isn't a homework problem.

  • $\begingroup$ What are typical values of $x$? Are allowed to allocate $O(n^2x)$ memory? $\endgroup$ – Vladislav Mar 13 at 17:50
  • $\begingroup$ If $A$ (or, sometimes we say $n$), $k$ and $x$ are variable, the problem is NP-hard. $\endgroup$ – John L. Mar 13 at 21:40
  • $\begingroup$ I'm confused. It appears that the values of the elements are irrelevant as the problem statement only refers to the indices of the elements but not their values. Can you edit the question to clarify what you are asking? What has to be less than $x$? $\endgroup$ – D.W. Mar 14 at 4:15

You can use meet-in-the-middle to reduce the running time to $O(n^{\lceil k/2 \rceil})$.

For simplicity, let me assume that $k$ is even.

The idea is as follows:

  • Partition $A$ into two parts.
  • For each part, compute a sorted list of sums of $k/2$ elements from the part.
  • For each $k/2$-sum in the first part, use binary search to find the best $k/2$-sum in the second part which conforms to the constraints.

As stated, there are several problems with the idea:

  1. It assumes that the optimal solution contains exactly $k/2$ summands out of each part.
  2. It runs in time $O(n^{k/2} \log n)$.
  3. It uses $O(n^{k/2})$ memory.

To handle the first difficulty, there are several options. We could just repeat the entire algorithm $\sqrt{k}$ times. Alternatively, there might be deterministic ways to achieve the same goal. Here is a hybrid solution:

  • Randomly partition $A$ into $k^3$ parts $P_1,\ldots,P_{k^3}$ (anything substantially larger than $k^2$ would work). With high probability, each element of the optimal solution is in its own part.
  • Consider all possible partitions of $A$ into two parts of the form $P_1,\ldots,P_i$ and $P_{i+1},\ldots,P_{k^3}$. One of these will contain exactly $k/2$ elements of the optimal solution.

To handle the second difficulty, we need to be slightly more careful in implementation. Using merging (the familiar subroutine from mergesort), it should be possible to compute the $k/2$-sums of each part in $O(n^{k/2})$. The final step can be implemented in $O(n^{k/2})$ using a classic two-pointer technique (the first pointer goes up on the first half, the second one goes down on the second half).

There are tricks to reduce the memory required from $O(n^{k/2})$ to $O(n^{k/4})$: further divide each part into two sub-parts. You can easily go over all $k/2$-sums in the first part by considering all pairs of $k/4$-sums in its subparts. Binary search on the second part can then be implemented using the two-pointer technique.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.