Tallest billboard

Array Dynamic Programming

51.8% acceptance

Feb 25, 2026

2464

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn tallest_billboard(rods: Vec<i32>) -> i32 {
    // dp[d] = max height of shorter side when |tall-short| = d
    let max_sum: usize = rods.iter().sum::<i32>() as usize + 1;
    let mut dp = vec![-1i32; max_sum];
    dp[0] = 0;
    for &r in &rods {
      let prev = dp.clone();
      for d in 0..max_sum {
        if prev[d] < 0 { continue; }
        let h = prev[d];
        // add to taller side
        if d + (r as usize) < max_sum {
          dp[d + r as usize] = dp[d + r as usize].max(h);
        }
        // add to shorter side
        let r = r as usize;
        if r <= d {
          dp[d - r] = dp[d - r].max(h + r as i32);
        } else {
          dp[r - d] = dp[r - d].max(h + d as i32);
        }
      }
    }
    dp[0]
  }
}