Question:
Given $n$ numbers $a_1,...,a_n$ find indices $i$ and $j$, $1 ≤ i ≤ j ≤ n$, such that $\sum\limits_{k=i}^{j}a_k$ is minimized. We will develop two algorithms for this problem that run in linear time, i.e., the number of (arithmetic) operations is linear in n.
Solve the problem using Bellman-Ford as a subroutine. In particular, construct a graph such that a shortest path in this graph yields the optimal solution to the above problem. Show that the graph can be generated in linear time and that Bellman-Ford can be implemented to run in linear time on this graph.
Answer:
My question:
Why is the second graph more efficient for the case where some of the $a_i$ are negative? I don't see the difference in those two graphs when it comes to the exercise...