algorithm - Tree Walks With Weighted Nodes -

given tree, nodes have value(can negative), find path maximizes sum of nodes in path.

i have tried using solution using dynamic programming techniques, can not break through.

we flood-fill algorithm on tree, starting each leaf, , running maximum subsequence sum algorithm on paths discover during flood-fill. produces candidate maximum value each pair of leaves; , choose largest of these our true answer. solution takes o(n^2) time: there o(n) leaves, , o(n) work flood-fill version of maximum-subsequence-sum problem on each leaf, yielding o(n^2) work total candidate production phase. o(n^2) work choose maximal path out of o(n^2) candidates have generated.

i give sample implementation in haskell. imports can ignore:

import data.list import data.monoid 

for simplicity, represent our tree function which, given node, tells weight , neighbors available. when naming types , terms, use w weights , n nodes.

type tree w n = n -> (w, [n]) 

it handy have way refer path , weight:

type weightedpath w n = (sum w, [n]) 

during our walk, keep 2 statistics, namely, maximal path ending @ current node, , maximal path we've seen far. we'll have constant "empty summary" corresponds empty tree: no paths, , 0 weight.

data summary w n = summary     { endinghere     :: weightedpath w n     , endinganywhere :: weightedpath w n     }  emptysummary :: num w => summary w n emptysummary = summary mempty mempty 

we'll need flood-fill algorithm. it's pretty simple, though parameterized "initial summary" , way extend summary 1 weighted node; because we'll using flood-fill algorithm both find leaves , find candidate paths. 1 trick we'll need watch make sure don't back-track; track previous node (if any) in nprevious purpose.

flood :: eq n => (w -> n -> s -> s) -> s -> tree w n -> n -> [s] flood extend summary t = go nothing summary     go nprevious summary ncurrent = case maybe id delete nprevious ns of         [] -> [summary']         ns -> ns >>= go (just ncurrent) summary'                 (w, ns)  = t ncurrent         summary' = extend w ncurrent summary 

for example, can find leaves making our "summary" last node saw. if tree empty, we'll throw our hands in disgust:

findleaves :: eq n => tree w n -> n -> [n] findleaves = flood (\w n s -> n) undefined 

we can extend path candidate summary 1 node in linked algorithm:

extend :: (num w, ord w, ord n) => w -> n -> summary w n -> summary w n extend w n s = answer     answer = s         { endinghere = max (0, []) ((sum w, [n]) <> endinghere s)         , endinganywhere = max (endinghere answer) (endinganywhere s)         } 

this function slots our flood-fill algorithm nicely find candidate paths starting particular node:

findcandidates :: (num w, ord w, ord n) => tree w n -> n -> [summary w n] findcandidates t n = findleaves t n >>= flood extend emptysummary t 

the top-level function flood-fill , picks maximum candidate. (ties broken arbitrarily, in extend.)

maximalpath :: (num w, ord w, ord n) => tree w n -> n -> weightedpath w n maximalpath t n = maximum . map endinganywhere $ findcandidates t n 

let's see run. we'll define simple sample tree: it's star-shaped tree, node 0 @ center , nodes 1 through 5 each connected central hub. center has weight -1, , leaves weighted 1 through 5 according node are.

sampletree :: tree int int sampletree 0 = (-1, [1..5]) sampletree n = (n, [0]) 

in ghci, can find find maximal path providing tree , node in tree:

> maximalpath sampletree 0 (sum {getsum = 8},[5,0,4]) 

...which says largest sum 8, , can achieved traveling path outer node 5 hub node 0, outward node 4.