Welcome to Subscribe On Youtube

956. Tallest Billboard

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

Solutions

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int tallestBillboard(int[] rods) {
          int n = rods.length;
          int s = 0;
          for (int x : rods) {
              s += x;
          }
          int[][] f = new int[n + 1][s + 1];
          for (var e : f) {
              Arrays.fill(e, -(1 << 30));
          }
          f[0][0] = 0;
          for (int i = 1, t = 0; i <= n; ++i) {
              int x = rods[i - 1];
              t += x;
              for (int j = 0; j <= t; ++j) {
                  f[i][j] = f[i - 1][j];
                  if (j >= x) {
                      f[i][j] = Math.max(f[i][j], f[i - 1][j - x]);
                  }
                  if (j + x <= t) {
                      f[i][j] = Math.max(f[i][j], f[i - 1][j + x] + x);
                  }
                  if (j < x) {
                      f[i][j] = Math.max(f[i][j], f[i - 1][x - j] + x - j);
                  }
              }
          }
          return f[n][0];
      }
  }
  

• class Solution {
  public:
      int tallestBillboard(vector<int>& rods) {
          int n = rods.size();
          int s = accumulate(rods.begin(), rods.end(), 0);
          int f[n + 1][s + 1];
          memset(f, -0x3f, sizeof(f));
          f[0][0] = 0;
          for (int i = 1, t = 0; i <= n; ++i) {
              int x = rods[i - 1];
              t += x;
              for (int j = 0; j <= t; ++j) {
                  f[i][j] = f[i - 1][j];
                  if (j >= x) {
                      f[i][j] = max(f[i][j], f[i - 1][j - x]);
                  }
                  if (j + x <= t) {
                      f[i][j] = max(f[i][j], f[i - 1][j + x] + x);
                  }
                  if (j < x) {
                      f[i][j] = max(f[i][j], f[i - 1][x - j] + x - j);
                  }
              }
          }
          return f[n][0];
      }
  };
  

• class Solution:
      def tallestBillboard(self, rods: List[int]) -> int:
          n = len(rods)
          s = sum(rods)
          f = [[-inf] * (s + 1) for _ in range(n + 1)]
          f[0][0] = 0
          t = 0
          for i, x in enumerate(rods, 1):
              t += x
              for j in range(t + 1):
                  f[i][j] = f[i - 1][j]
                  if j >= x:
                      f[i][j] = max(f[i][j], f[i - 1][j - x])
                  if j + x <= t:
                      f[i][j] = max(f[i][j], f[i - 1][j + x] + x)
                  if j < x:
                      f[i][j] = max(f[i][j], f[i - 1][x - j] + x - j)
          return f[n][0]
  
  

• func tallestBillboard(rods []int) int {
  	n := len(rods)
  	s := 0
  	for _, x := range rods {
  		s += x
  	}
  	f := make([][]int, n+1)
  	for i := range f {
  		f[i] = make([]int, s+1)
  		for j := range f[i] {
  			f[i][j] = -(1 << 30)
  		}
  	}
  	f[0][0] = 0
  	for i, t := 1, 0; i <= n; i++ {
  		x := rods[i-1]
  		t += x
  		for j := 0; j <= t; j++ {
  			f[i][j] = f[i-1][j]
  			if j >= x {
  				f[i][j] = max(f[i][j], f[i-1][j-x])
  			}
  			if j+x <= t {
  				f[i][j] = max(f[i][j], f[i-1][j+x]+x)
  			}
  			if j < x {
  				f[i][j] = max(f[i][j], f[i-1][x-j]+x-j)
  			}
  		}
  	}
  	return f[n][0]
  }
  

• function tallestBillboard(rods: number[]): number {
      const s = rods.reduce((a, b) => a + b, 0);
      const n = rods.length;
      const f = new Array(n).fill(0).map(() => new Array(s + 1).fill(-1));
      const dfs = (i: number, j: number): number => {
          if (i >= n) {
              return j === 0 ? 0 : -(1 << 30);
          }
          if (f[i][j] !== -1) {
              return f[i][j];
          }
          let ans = Math.max(dfs(i + 1, j), dfs(i + 1, j + rods[i]));
          ans = Math.max(ans, dfs(i + 1, Math.abs(j - rods[i])) + Math.min(j, rods[i]));
          return (f[i][j] = ans);
      };
      return dfs(0, 0);
  }
  
  

All Problems

All Solutions