5
$\begingroup$

Given an integer sequence $\{ a_1, a_2, \ldots, a_N \}$ that has length $N$ and a fixed integer $M\leq N$, the problem is to find a subset $A =\{i_1, \dots, i_M\} \subseteq [N]$ with $1 \leq i_1 \lt i_1 \lt \dots \lt i_M \leq N$ such that

$\qquad \displaystyle \sum_{j=1}^M j \cdot a_{i_j}$

is maximized.


For instance, if the given sequence is $-50; 100; -20; 40; 30$ and $M = 2$, the best weighted sum arises when we choose positions 2 and 4.

So that we get a value $1 \cdot 100 + 2 \cdot 40 = 180$.

On the other hand, if the given sequence is $10; 50; 20$ and $M$ is again 2, the best option is to choose positions 1 and 2 that we get a value $1 \cdot 10 + 2 \cdot 50 = 110$.


To me it looks similar to the maximum subarray problem, but I can think of many examples in which the maximum subarray is not the best solution.

Is this problem an instance of a well studied problem? What is the best algorithm to solve it?

This question was inspired by this StackOverflow question.

$\endgroup$
  • $\begingroup$ What constraints are imposed on the sequence $a_1,\ldots,a_n$? $\endgroup$ – Dave Clarke Jun 2 '12 at 15:21
  • 1
    $\begingroup$ I do not understand your example 1. Should not that be $2 \cdot 100 + 4 \cdot 40$? And example 2 be $2 \cdot 50 + 3 \cdot 20$? $\endgroup$ – Dmitri Chubarov Jun 2 '12 at 15:42
  • 1
    $\begingroup$ Your examples do not appear to match the sum you have defined... $\endgroup$ – David Jun 2 '12 at 15:44
  • 1
    $\begingroup$ That they are integers is sufficient (that is a constraint in itself). $\endgroup$ – Dave Clarke Jun 2 '12 at 15:57
  • 1
    $\begingroup$ Your summation (in revision 3) in condition 2 does not make sense. Why don’t you write exactly as defined in the PDF? $\endgroup$ – Tsuyoshi Ito Jun 2 '12 at 16:12
5
$\begingroup$

This problem can be solved by means of dynamic programming. One of the best known dynamic programming algorithms is for the knapsack problem. It may be instructive to compare the two problems.

Let $C(n,m)$ denote the solution to the maximal weighted sum problem for the sequence $a_1, a_2, \ldots a_n$ with a subsequence of length $m$ where $1\leq n\leq N$ and $1\leq m\leq M$.

Then $C(n,m+1) = \mathop{max}(C(n-1,m+1), C(n-1,m) + (m+1) \cdot a_n)$.

To compute $C(N,M)$ this algorithm can be implemented in $O(N M)$ time and $O(N)$ space.

$\endgroup$
  • 1
    $\begingroup$ Note that if you want to obtain $A$, you need $\Theta(NM)$ space, too; you have to keep all computed values plus predecessor information for backtracking (or, alternatively, paths of length $\Theta(N)$ in each of the $\Theta(N)$ maintained values). $\endgroup$ – Raphael Jun 3 '12 at 12:18

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.