0956. Tallest Billboard

题目信息

题号:

0956

难度:

Hard

主题:

钢条分配、等高支架、最大高度

原题:

LeetCode 0956

重点:

每根钢条只能分配给左支架、右支架或不使用;两侧总长度必须相等,返回这个共同长度的最大值

题目重述

给定正整数数组 rods,每个元素表示一根钢条的长度。需要选择其中若干钢条并把每根被选钢条完整地放到左支架或右支架,不能切割;也允许某些钢条不使用。

当左右两侧钢条长度总和相等时,可以支撑广告牌,该相等总和就是广告牌高度。请返回能够得到的最大高度;若无法形成正高度的等长两侧,返回 0。

1 <= rods.length <= 20,1 <= rods[i] <= 1000,所有钢条长度总和不超过 5000。

自建示例

四根钢条全部使用:

输入:rods = [1,2,3,4]
输出:5
解释:一侧使用 1 和 4,另一侧使用 2 和 3,两侧总长都为 5;不存在更高的等长分配。

只有一根钢条:

输入:rods = [5]
输出:0
解释:钢条不能切割,一根钢条无法同时分配到左右两侧,因此不能形成正高度的等长支架。