FastPrepFastPrep
Problem Brief

Best Sum Downward Tree Path

NEW GRADOA

For a tree with n nodes rooted at node 0 (nodes numbered from 0 to n-1), where each node i has a value given by values[i], determine the maximum sum of values along any path that starts at a node u and only goes downward in the tree.

Consider only paths of the form u₁, u₂, u₃, ..., uₖ where each node uᵢ is a child of node uᵢ₋₁ for 1 < i ≤ k. For example, given the following tree (labeled node number/value):

Two possible paths are 0 → 1 → 2 → 3 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.

Function Description

Complete the function bestSumDownwardTreePath in the editor with the following parameter(s):

  1. int parent[n]: each parent[i] represents the parent node for node i, parent[i] = -1 means node i is the root
  2. int values[n]: each values[i] represents the value of node i

Returns

int: the largest sum of values along a path down the tree from any node u

1Example 1

Input
capacity = [9, 3, 3, 3, 9]
Output
2
Explanation
There are 2 stable subsegments: [3, 3, 3] and [9, 3, 3, 3, 9]. Return 2.

Constraints

Limits and guarantees your solution can rely on.

  • 1 ≤ n ≤ 10⁵
  • parent[0] = -1
  • 0 ≤ parent[i] < n-1 for 0 < i < n-1
  • -1000 ≤ values[i] ≤ 1000
  • the tree described is valid
public int bestSumDownwardTreePath(int[] parent, int[] values) {
  // write your code here
}
Input

capacity

[9, 3, 3, 3, 9]

Output

2

Sign in to submit your solution.