0
$\begingroup$

The finite sequence of integers $Y_1, \dots, Y_M$ takes both positive and negative values, where $M$ is a fixed positive integer. Could you help me to find a formulation using dynamic programming that solves the problem of finding integers $i_1, i_2$ with $1 \leq i_1 \leq i_2 \leq M$ such that the sum $\sum_{j=i_1}^{i_2} Y_j$ gets minimized?

I have thought the following:

We define $s_0^{\star}(i)=Y_i , \ \ \forall i=1, \dots, M$.

Also $s_i^{\star}(j)= \min_k \{ s_{i-1}^{\star}(j)+Y_k\}$.

But we have to take into consideration that we cannot pick a $J_k$ for $s_i^{\star}(j)$ if we have already used it to get $s_{i-1}^{\star}(j)$.

How can we include this in the formula?

Could you give me a hint?

$\endgroup$
2
$\begingroup$

There is no need to use dynamic programming for this problem. Set $S_i = \sum \limits_{n = 1}^i Y_i$ [where $S_0 = 0$] and note that the minimal sum is $\min\{S_i - \max\{S_j \mid 1 \le j < i\} \mid 2 \le i \le M\}$. From this formula, you can create a program that solves the problem in linear time.

$\endgroup$
1
  • $\begingroup$ But what formula could we use if we want to use dynamic programming? $\endgroup$ – Evinda Jan 9 '16 at 21:37

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.