Tallest Billboard — LeetCode 956 Python Solution

The problem

You are installing a billboard and want it to have the largest height. The billboard will have two steel supports, one on each side.

Example

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.

Python solution

class Solution:
    def tallestBillboard(self, rods: List[int]) -> int:
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= len(rods):
                return 0 if j == 0 else -inf
            ans = max(dfs(i + 1, j), dfs(i + 1, j + rods[i]))
            ans = max(ans, dfs(i + 1, abs(rods[i] - j)) + min(j, rods[i]))
            return ans

        return dfs(0, 0)

Complexity

Pattern: Dynamic Programming

Define a state, write the transition, and stop recomputing the same subproblem. LeetCode 956. Tallest Billboard is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Dynamic Programming.

The dynamic programming guide has the Python template for the pattern and the 481 LeetCode problems that use it.

Related problems