3
$\begingroup$

Write an algorithm that, given sequence seq of n numbers where 3 <= n <= 1000 and each number k in seq 1 <= k <= 200, finds maximum sum by repeatedly removing one number from seq, except for first and last number in seq, and adding its value to sum of two adjacent numbers. Algorithm ends when there are only two numbers left.

For example:
[2, 1, 5, 3, 4], sum = 0
[2, 1, 5, 3, 4], sum = 1 + 2 + 5 = 8, 1 removed
[2, 5, 3, 4], sum = 8 + 3 + 5 + 4 = 20, 3 removed
[2, 5, 4], sum = 20 + 5 + 2 + 4 = 31, 5 removed
[2, 4] only 2 numbers left so algorithm ends

So far I've written brute force algorithm checking all possible combinations but it's not well suited for large sequences.

My question is, is there more efficient algorithm solving this problem?

$\endgroup$
  • $\begingroup$ I think you need to extend your example at least - it's unclear how your summation works $\endgroup$ – HEKTO Oct 8 at 19:16
  • $\begingroup$ @HEKTO I've extended the example, If something is still unclear, please let me know. $\endgroup$ – Shyver Oct 8 at 19:45
  • $\begingroup$ Did you try dynamic programming? $\endgroup$ – HEKTO Oct 8 at 20:17
  • $\begingroup$ @HEKTO I've tried approach with memoization but due to seqence beeing this recursive function argument (every time you pass sequence with one number less than previous) and copying it before each call causes a lot of overhead. And I have to use map with sequence (or its representation as e.g. string) as cache which adds additional overhead due to iterating over sequence. Or maybe I don't understand something fully. $\endgroup$ – Shyver Oct 8 at 21:40
  • 1
    $\begingroup$ Try to use dynamic programming and to define $OPT[i,j]$ with $1\le i \le j \le n$ as the value of the optimal solution to the instance of your problem consisting of the $i$-th to $j$-th input numbers. See also this question. $\endgroup$ – Steven Oct 9 at 1:57
2
$\begingroup$

I'll explain the Dynamic Programming approach to your problem using your sample sequence $[2,1,5,3,4]$. This approach is based on analysis of sub-problems - in your case each sub-problem is simply a task to find the maximal value (in the sense you described in your question) for some sub-sequence. These sub-problems are related to each other - this reducibility relation means that one sub-problem can be reduced to another one in a single step. For example, the sub-problem $[2,1,5,3,4]$ can be reduced to sub-problems $[2,5,3,4]$, $[2,1,3,4]$ and $[2,1,5,4]$ by removing a single number from the sequence.

The graph of sub-problems with this reducibility relationship is below. It's easy to see that our problem is equivalent to a problem of finding a path from the vertex $[2,1,5,3,4]$ to the vertex $[2,4]$ (or vice versa), which will give us the maximal value for the vertex $[2,1,5,3,4]$ (see the path, marked by red color).

Graph of sub-problems

Not every problem can be solved by decomposition into sub-problems - such a problem must have Optimal Substructure for that. In our case it means that all the sub-problems along the optimal reducibility path must also have optimal solution. For example, the value of the vertex $[2,5,3,4]$ can be calculated along two paths, so we need to choose the maximal value (23) along the red path and forget about another path.

This local optimization is the reason why the Dynamic Programming method works so well for large problems. It often allows us to reduce exponential time complexity to polynomial one.

There are two ways to solve our problem using Dynamic Programming - "top-to-bottom" and "bottom-up". In our case they are equivalent to traversing our graph from the vertex $[2,1,5,3,4]$ to the vertex $[2,4]$ or vice versa.

  • The top-to-bottom way involves developing a recursive function with two arguments - a sub-problem description (sub-sequence in our case), and mapping from the sub-problem description to the values space. This mapping will gather information about already solved sub-problems, so we will never solve the same problem again. The function will need to reduce (in one step!) the given sub-problem to all the possible sub-sub-problems and find the maximum of calculated values. Using such a mapping is often called Memoization.

  • The bottom-up way starts from the simplest sub-problem ($[2,4]$ with value = 0) and assigns values to all the sub-problems going up layer by layer, again maximizing the value of each sub-problem, calculated over its sub-sub-problems. Here we don't need recursion, however multiple nested loops will be needed, and it's not easy to program that correctly right away.

Now - it's your job to choose a way you want and solve your problem in general case.

ADDITION. We can make our graph oriented (each arc is oriented from top to bottom) and weighted (each arc weight is equal to the portion of value, given by its beginning) - then the described above "bottom-up" approach becomes equivalent to the Longest Path in Acyclical Digraph Problem.

$\endgroup$
0
$\begingroup$

$$ \mathrm{OPT}[i,j] = \begin{cases} \max_{h\in\{i+1,\dots,j-1\}} \left\{\mathrm{seq}[i] + \mathrm{seq}[h] + \mathrm{seq}[j] + \mathrm{OPT}[i,h] + \mathrm{OPT}[h,j]\right\} &\mbox{if } j-i > 1 \\ 0 & \mbox{if } j-i = 1 \end{cases} $$ where $1\le i<j\le n$.

Thank you all for your advices, especialy @Steven for providing link to another question.

$\endgroup$

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.