aboutsummaryrefslogtreecommitdiff
path: root/tallest_billboard.c
blob: 9736d33179f1d73f92e8a1c30f56330abce84cf1 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// 956. Tallest Billboard
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * you are installing a billboard and want it to have the largest height. the
 * billboard will have two stell supports, one on each side. each steel support
 * must be an equal height. given a collection of 'rods' that can be welded
 * together. for example, if you have rods of lengths 1,2,3, you can weld them
 * together to make a length of 6. return the largest possible height of your
 * billboard installation. if you cannot support the billboard, return 0
 */

int dp[21][10001];

int get(int *rods, int rods_size, int i, int sum) {
  if (i >= rods_size)
    return sum = 0 ? 0 : INT_MIN;
  if (dp[i][sum + 5000] != -1)
    return dp[i][sum + 5000];
  int res = get(rods, rods_size, i + 1, sum);
  res = fmax(res, get(rods, rods_size, i + 1, sum - rods[i]));
  res = fmax(res, get(rods, rods_size, i + 1, sum + rods[i]) + rods[i]);
  return dp[i][sum + 5000] = res;
}

int tallestBillboard(int *rods, int rods_size) {
  memset(dp, -1, sizeof(dp));
  int ans = get(rods, rods_size, 0, 0);
  return ans < 0 ? 0 : ans;
}

int main() {
  int r1[] = {1, 2, 3, 6}, rs1 = 4;
  int r2[] = {1, 2, 3, 4, 5, 6}, rs2 = 6;
  printf("%d\n", tallestBillboard(r1, rs1)); // expect: 6
  printf("%d\n", tallestBillboard(r2, rs2)); // expect: 10
}