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?
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.