HomeVolumesContestsSectionsForumsUsersPrintHelpAbout

Sections > Divide&Conquer and Binary Search Trees (BST) > problem:


50816 - Largest Sum Path

Guest
• Review clarifications (1)

Section problems

• 50770 - Average Depth
• 50411 - Sum of the Leaves
• 50830 - Sorting BST Nodes
• 50803 - Sum of the depths in BST
• 50805 - Sum of the weights in a BST
• 50818 - Depth Limited BST
• 50836 - Censored
• 50816 - Largest Sum Path
• 50772 - The Path of a Node
• 50863 - Total Access Cost of a BST
• 50771 - BST Level Sum
• 50773 - Balanced Sum Tree
• 50722 - Scientist's problem

Feedback

If you notice incorrect translations in Contester, please let author know.

Time limit 2000/4000/4000/4000 ms. Memory limit 65000/65000/65000/65000 Kb.
Question by Ibrahim Mesecan.

Largest Sum Path

Path sum is the sum of the numbers on a path in BST. For example the sum of the numbers 

  15 + 12 + 14 + 13 = 54
is the largest path sum according to the given BST.

Question: Write a program to find the largest path sum in a given BST.

Input specification
In the first line, you will be given an integer (n) The number of numbers in the BST where 0 ≤ n ≤ 1e4. Then, in the following n lines, you will be given n integers which are between -1e4 and 1e4.

Output specification
Show one number: Largest path sum.

Sample Input I
10
15
17
15
12
14
12
16
1
17
13
Sample Output I
54



Для отправки решений необходимо выполнить вход.

www.contester.ru