Note “path” implies directed (not bidirectional) edges i.e. dag
- variation (rare): bi-directional edges
- variation: single origin, single destination
- variation: single origin, any destination among 55 leaf nodes
- variation: each node has a +/- value
- variation (rare): each edge has a +/- value. Edges usually outnumber nodes, as illustrated in the balloon-burst problem
–Common Special case: pyramid (see blogpost on recombinant binTree). The balloon problem has high fan-out.
I would try DP. For each node AA, determine (and store) the max cum-sum up to AA. Need to start from the layer 1 nodes (1 hop from origin), then use Layer 1 data to update layer 2 nodes.
Markov-like — For any node AA, the max cum-sum to AA only depends on the previous layer. No need to even care about a “fullpath” to AA. This property leads to dramatic *simplification*. Efficiency is a by-product of this simplification.
–Common Special case: non-recombinant binary tree.
i would use DFT + Kadane. Each origin-to-leaf path is independently handled. No layering.
Note Kadane algo handles +/- node values.