P14131.【递归3】完全二叉树的最大路径和

2000ms

Difficulty: 6

算法与标签>递归

题目描述：

给定一个数组表示一颗完全二叉树的节点值，其中数组下标 $i$ 对应的节点值为 $arr[i]$ ，左子节点的下标为 $2i + 1$ ，右子节点的下标为 $2i + 2$ 。你需要求出所有从根节点到叶子节点路径的最大路径和。

路径的定义是从根节点到任意叶子节点的路径，每个节点的值加上当前节点的值。

请你实现一个递归算法来计算所有路径中的最大路径和。

输入的第一行是一个整数 $n$ ( $1 \leq n \leq 10^5$ )，表示数组 $arr$ 的长度。
第二行是 $n$ 个整数 $arr_0, arr_1, ..., arr_{n-1}$ ( $1 \leq arr[i] \leq 10^5$ )，表示完全二叉树的节点值。

5
1 2 3 4 5

输入

预期输出（选填）

【递归3】完全二叉树的最大路径和