956. 最高的广告牌

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。

你有一堆可以焊接在一起的钢筋 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);
    }
}