Company: IBM
Difficulty: medium
Maximum Sum Downward Tree Path Given a tree with n nodes, rooted at node 0 (nodes are numbered from 0 to n-1 ), with values assigned to nodes such that values[i] denotes the value of node i , find the maximal sum of values along any path starting at some node u and going only down the tree. In other words, only consider paths u 1 , u 2 , ..., u k where each node u i is a child of node u i-1 for 1 ≤ i ≤ k . For example, given the following tree (labeled node number / value): Two possible paths are 0 → 1 → 2 which has a sum of 5 + 7 + (-10) + 4 = 6 and 1 → 2 → 3 with a sum of 7 + (-10) + 4 = 1 . The highest sum path is 0 → 4 with a sum of 5 + 15 = 20 . Input Format Complete the function bestSumDownwardTreePath in the editor below. It must return an integer that denotes the largest sum of values along a path down the tree from any node u . bestSumDownwardTreePath has the following parameters: parent[parent[0], parent[1], ..., parent[n-1]] : an array of integers where each parent[i] repres