Interview Question

Software Engineer Interview(Student Candidate) Hangzhou, Zhejiang (China)

given a tree, with a number assigned to each node, and a

  size N, find the maximum subtree such that: a. it contains N nodes, b. maximizes sum of nodes in the subtree
Tags:
c++ programming
Answer

Interview Answer

1 Answer

1

DP on tree, M[a][k] = maximum{ M[a.left][i]+M[a.right][N-i-1]+(i==N?0:num[a]), i=0..N }

Interview Candidate on Apr 9, 2012

Add Answers or Comments

To comment on this question, Sign In with Facebook or Sign Up