文章目录
前言
解题思路
代码
前言
你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。
你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。
返回 广告牌的最大可能安装高度 。如果没法安装广告牌，请返回 0
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/tallest-billboard
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
解题思路
定义一个map
key:随意选两个子集产生的差值
在数组没有遍历之前，能够找到两个集合， 空集对空集，差值为0
value:有可能会有多个集合对产生同样的差值,记录产生当前差值那一对较好那一对集合较小的那个
谁的值大，谁是较好的一对
关心谁?基线最高的那个
3出现了,加工出map:在只考虑3的情况下，会有哪些差值产生
我老map是所有可能的集合所有可能的插值中最好的一对。
我新map是考虑了当前数字，对每一个老的集合接近左进右出来的新纪录。
我最终的新map怎么合并?老map和新map中的记录，综台起来，最好的变成新map,继续往下推。
当你推过了所有的数字，最终的map你看差值为0的最好一对就是你要的
为什么map中把所有差值都要记录?
那是因为你后面不知道会遇到什么数字。
举个例子，你最后一个数是一百万， 特别大，极大，它左边的数都没它大，但它是一百万。在来到1百万之前，我这个map千变万化，map中有可能有一 个差值是1百万，基线相当的高。
你遇到最后一个数字的时候，它1百万的差值代表什么?
比如说在你来到最后数字之前map里面有一个插值是1百万的基线10亿，
这说明有一一个集合它{10亿+ 100万},还有集合叫{10亿}。这时候你的一百万进去，
正好怼出一个差值为零的来。
所以为什么map要记录所有的差值，你不知道后面哪一个奇葩数能拱出大的来,
我不知道后面有什么奇葩的数，能让我一个重新插值为季的集合基线变得巨大,
不知道，所以我都留着。
代码
class Solution {
public int tallestBillboard(int[] rods) {
HashMap<Integer,Integer> dp=new HashMap<>(),cur;
dp.put(0,0);
for(int num:rods){
if(num!=0){
cur=new HashMap<>(dp);
for(int d:cur.keySet()){
int diffMore=cur.get(d);
dp.put(d + num, Math.max(diffMore, dp.getOrDefault(num + d, 0)));
int diffXD=dp.getOrDefault(Math.abs(num-d),0);
if(d>=num){
dp.put(d-num,Math.max(diffMore+num,diffXD));
}else{
dp.put(num-d,Math.max(diffMore+d,diffXD));
}
}
}
}
return dp.get(0);
}
}
