Description
You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side. Each steel support must be an equal height.
You are given a collection of rods that can be welded together. For example, if you have rods of lengths 1, 2, and 3, you can weld them together to make a support of length 6.
Return the largest possible height of your billboard installation. If you cannot support the billboard, return 0.
Example 1:
Input: rods = [1,2,3,6]
Output: 6
Explanation: We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.
Example 2:
Input: rods = [1,2,3,4,5,6]
Output: 10
Explanation: We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.
Example 3:
Input: rods = [1,2]
Output: 0
Explanation: The billboard cannot be supported, so we return 0.
Constraints:
1 <= rods.length <= 20
1 <= rods[i] <= 1000
sum(rods[i]) <= 5000
Approach
The code uses dynamic programming to solve the problem. It maintains a dictionary dp, where the keys represent the possible height differences between the two billboards, and the values represent the maximum sum of heights achieved for each height difference.
The code iterates through each rod in the given input rods. For each rod i, it creates a new dictionary cur to store the updated values for dp. Then, it iterates through the existing entries in dp and updates the values in cur based on three cases:
Adding the current rod i to the same height difference: cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])
Keeping the same height difference: cur[sum] = max(dp[sum]!, cur[sum, default: 0])
Subtracting the current rod i from the height difference: cur[sum - i] = max(dp[sum]!, cur[sum - i, default: 0])
After iterating through all the rods, the final result is obtained from dp[0], which represents the maximum possible sum of heights for a height difference of 0 (i.e., the two billboards have equal heights).
Complexity
Time complexity: O(n * m).
Code (Swift)
class Solution {
func tallestBillboard(_ rods: [Int]) -> Int {
var dp = [0: 0]
for i in rods {
var cur = [Int: Int]()
for (sum, height) in dp {
cur[sum + i] = max(dp[sum]! + i, cur[sum + i, default: 0])
cur[sum] = max(dp[sum]!, cur[sum, default: 0])
cur[sum - i] = max(dp[sum]!, cur[sum - i, default: 0])
}
dp = cur
}
return dp[0, default: 0]
}
}Sources: Github
