Formatted question description: https://leetcode.ca/all/956.html

# 956. Tallest Billboard (Hard)

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 have a collection of `rods`

which 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:[1,2,3,6]Output:6Explanation:We have two disjoint subsets {1,2,3} and {6}, which have the same sum = 6.

**Example 2:**

Input:[1,2,3,4,5,6]Output:10Explanation:We have two disjoint subsets {2,3,5} and {4,6}, which have the same sum = 10.

**Example 3:**

Input:[1,2]Output:0Explanation:The billboard cannot be supported, so we return 0.

**Note:**

`0 <= rods.length <= 20`

`1 <= rods[i] <= 1000`

`The sum of rods is at most 5000.`

**Related Topics**:

Dynamic Programming

## Solution 1. DP

### Thought

For each rod `x`

, we have 3 options:

- use it in one post
- use it in another post
- don’t use it.

If we turn all the numbers used in the first post to negative (turn `x`

to `-x`

), leave the numbers used in the second post as-is (`x`

to `+x`

), and turn all the numbers that are not used to `0`

, this question turns into:

Find the max score we can get after doing the above operations. The “score” is the sum of all the positive numbers. For example, `+1 +2 +3 -6`

has a score of `6`

.

Since `sum(rods)`

is bounded, it suggests us to use this fact in some way.

A fact we should consider is that for a given `sum`

, it doesn’t matter how we get the `sum`

.

For example, with `rods = [1,2,2,3]`

, we could get sum `3`

in 3 different ways. If we just consider `sum = 3`

, we actually covered all those three cases.

Since `sum`

is in range `[-5000, 5000]`

, we just have `10001`

numbers to consider.

### Algorithm

Let `dp[i][s]`

be the largest score we can get using `rods[(i+1)..(N-1)]`

to get sum `s`

.

For example, for `rods = [1,2,3,6]`

, we have `dp[1][1] = 5`

, because after writing `1`

, we could write `+2 +3 -6`

to get sum `1`

, and the corresponding score is `5`

.

For the base case, `dp[rods.length][s]`

is `0`

when `s == 0`

, and `-infinity`

everywhere else.

The recursion is `dp[i][s] = max(dp[i+1][s], dp[i+1][s-rods[i]], rods[i] + dp[i+1][s+rods[i]])`

.

NOTE: in the following implementation we use `sum = 5000`

as `sum = 0`

to simply code.

```
// OJ: https://leetcode.com/problems/tallest-billboard
// Time: O(NS) where N is the length of `rods`,
// and S is the maximum of `sum(rods[i..j])`
// Space: O(NS)
// Ref: https://leetcode.com/articles/tallest-billboard/
class Solution {
private:
vector<vector<int>> dp;
int dfs(vector<int>& rods, int i, int s) {
if (i == rods.size()) return s == 5000 ? 0 : INT_MIN;
if (dp[i][s] != INT_MIN) return dp[i][s];
int ans = dfs(rods, i + 1, s);
ans = max(ans, dfs(rods, i + 1, s - rods[i]));
ans = max(ans, rods[i] + dfs(rods, i + 1, s + rods[i]));
return dp[i][s] = ans;
}
public:
int tallestBillboard(vector<int>& rods) {
int N = rods.size();
dp = vector<vector<int>>(N, vector<int>(10001, INT_MIN));
return dfs(rods, 0, 5000);
}
};
```

Java

```
class Solution {
public int tallestBillboard(int[] rods) {
int rows = rods.length;
if (rows < 2)
return 0;
int sum = 0;
for (int rod : rods)
sum += rod;
int columns = sum * 2 + 1;
int[][] dp = new int[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++)
dp[i][j] = -1;
}
dp[0][sum + rods[0]] = rods[0];
dp[0][sum] = 0;
dp[0][sum - rods[0]] = 0;
for (int i = 1; i < rows; i++) {
for (int j = 0; j < columns; j++) {
if (dp[i - 1][j] >= 0) {
int rod = rods[i];
dp[i][j + rod] = Math.max(dp[i][j + rod], dp[i - 1][j] + rod);
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
dp[i][j - rod] = Math.max(dp[i][j - rod], dp[i - 1][j]);
}
}
}
int maxHeight = 0;
for (int i = 0; i < rows; i++)
maxHeight = Math.max(maxHeight, dp[i][sum]);
return maxHeight;
}
}
```