Hey guys, this quick problem popped into my head:
You are given a DAG, where each node has an integer value (which may be negative). You can choose an arbitrary subset of nodes, as long as this constraint holds: if you pick a node, you also have to pick all nodes reachable from that node. Obtain the maximum possible value sum.
It feels like an NP problem to me, but I couldn't prove it. Anyone heard about it? Any ideas on how to solve it?