|
| 1 | +classSolution { |
| 2 | +publicinttallestBillboard(int[]rods) { |
| 3 | +intn =rods.length; |
| 4 | +Map<Integer,Integer>firstHalf =helper(rods,0,n /2); |
| 5 | +Map<Integer,Integer>secondHalf =helper(rods,n /2,n); |
| 6 | +intresult =0; |
| 7 | +for (Integerdifference :firstHalf.keySet()) { |
| 8 | +if (secondHalf.containsKey(-1 *difference)) { |
| 9 | +result =Math.max(result,firstHalf.get(difference) +secondHalf.get(-1 *difference)); |
| 10 | + } |
| 11 | + } |
| 12 | +returnresult; |
| 13 | + } |
| 14 | + |
| 15 | +privateMap<Integer,Integer>helper(int[]rods,intleftIdx,intrightIdx) { |
| 16 | +Set<Pair<Integer,Integer>>states =newHashSet<>(); |
| 17 | +states.add(newPair(0,0)); |
| 18 | +for (inti =leftIdx;i <rightIdx;i++) { |
| 19 | +introd =rods[i]; |
| 20 | +Set<Pair<Integer,Integer>>newStates =newHashSet<>(); |
| 21 | +for (Pair<Integer,Integer>state :states) { |
| 22 | +newStates.add(newPair(state.getKey() +rod,state.getValue())); |
| 23 | +newStates.add(newPair(state.getKey(),state.getValue() +rod)); |
| 24 | + } |
| 25 | +states.addAll(newStates); |
| 26 | + } |
| 27 | +Map<Integer,Integer>dp =newHashMap<>(); |
| 28 | +for (Pair<Integer,Integer>pair :states) { |
| 29 | +Integerleft =pair.getKey(); |
| 30 | +Integerright =pair.getValue(); |
| 31 | +dp.put(left -right,Math.max(dp.getOrDefault(left -right,0),left)); |
| 32 | + } |
| 33 | +returndp; |
| 34 | + } |
| 35 | +} |