DAG for contiguous subsequence of maximum sum
You grasped the idea right. For the problem of finding &quot;contiguous subsequence of maximum sum&quot;, the DAG is indeed $a_1 \to a_2 \to ... \to a_n$, since the sequence is contiguous.
To get a better feel for DAG, you should consider the problem of finding an &quot;increasing subsequence of maximum sum&quot; problem. By increasing subsequence, I mean that $a_{i} \leq a_{j}$ for any two consecutive elements $a_{i}$ and $a_{j}$ in the sequence.
Note that, an increasing subsequence might not be contiguous. And, to calculate $S(i)$, you will need $S(j)$ such that $a_{j}\leq a_{i}$. So there will be an edge between the nodes $j$ and $i$ if and only if $a_{j}\leq a_{i}$ and $j &lt; i$. You will get your DAG. Here, DAG might not contain the edges between $a_{i}$ and $a_{i+1}$, as it was in the previous problem.
You can also consider the problem of finding the &quot;subsequence of maximum sum&quot;. Here the subsequence is neither contiguous nor increasing. Here DAG will contain an edge between every pair of nodes $a_{i}$ and $a_{j}$ for $i&lt;j$. And, the maximum value is trivially the sum of all positive values in the array.