数组操作面试题：求解树木浇水后的最大高度

问题规则回顾 #

• 初始树木高度H=0，每个玻璃杯的水X只能使用一次，顺序可任意调整
• 若X > 当前H，树木高度H += X；否则H不变
• 目标是最大化最终H

错误思路分析 #

你之前采用的「升序排序后依次选择能加入的元素」是局部贪心策略，无法得到全局最优。比如测试用例[1,4,5,7,9]，该策略得到总和12，但实际存在更优的组合（如1+7+9=17），原因是跳过部分较小元素后，后续更大的元素能满足加入条件，最终总和更高。

正确解法：动态规划 #

我们可以通过动态规划枚举所有满足条件的子集，找到最大的可能总和：

核心思路

1. 排序数组：将数组从小到大排序，因为最优子集必然是按从小到大的顺序使用（先使用小元素，才能让后续大元素满足X>H的条件）。
2. 动态规划状态定义：用布尔数组dp，dp[s]表示是否能通过选择满足条件的子集，得到总和s（即该子集按顺序使用时，每个元素都大于之前的总和）。
3. 状态转移：遍历每个元素x，倒序遍历当前所有可能的总和s，若s可达到且x > s，则s+x也可达到（因为先使用得到s的子集，再使用x，满足x > s的条件）。
4. 找最大总和：从数组总总和开始往下查找，第一个dp[s]为True的s就是最大高度。

代码实现（Python）

def max_tree_height(n, arr):
    arr.sort()
    total_sum = sum(arr)
    dp = [False] * (total_sum + 1)
    dp[0] = True  # 初始状态：总和0（空子集）可达到
    
    for x in arr:
        # 倒序遍历避免重复使用同一元素
        for s in range(total_sum - x, -1, -1):
            if dp[s] and x > s:
                dp[s + x] = True
    
    # 寻找最大的有效总和
    for s in range(total_sum, -1, -1):
        if dp[s]:
            return s

测试验证

• 示例1：输入n=3, arr=[2,1,2]，排序后为[1,2,2]，最终返回3，符合预期。
• 测试用例arr=[1,4,5,7,9]，最终返回17，这是最优解（子集[1,7,9]，按顺序使用：1>0→H=1，7>1→H=8，9>8→H=17）。

内容的提问来源于stack exchange，提问作者pavanayi420