给定一个排序数组表示二叉树中序遍历的节点值，以及每个节点对应的权值，请设计算法在所有可能的中序遍历为该数组的二叉树中，找出权值之和最大的一棵，并说明其时间复杂度和思路。
考察说明
考察动态规划在树形结构优化中的应用，以及中序遍历约束下的状态定义
回答思路
- 识别出问题可转化为区间DP，枚举根节点分割左右子树
- 定义dp[i][j]为区间[i,j]构成的子问题最大权值和，状态转移包含根节点权值加左右子区间
- 正确处理边界条件，空区间权值为0
- 分析时间复杂度为O(n^3)，并说明可优化为O(n^2)
- 给出示例数组的计算过程或最终答案
本题已收录答题指导
本题附完整参考答案与评分标准
登录后可查看结构化答题指导；也可以直接开一场模拟面试，AI 面试官用本题实时追问并给出评分。