1
/**
2
 * @param {number[]} rods
3
 * @return {number}
4
 */
5
var tallestBillboard = function (rods) {
6
  let len = rods.length;
7
  if (len <= 1) return 0;
8
  let dp = [];
9
  for (let i = 0; i < len + 5; i++) {
10
    dp[i] = [];
11
    for (let j = 0; j < 5005 * 2; j++) {
12
      dp[i][j] = -1;
13
    }
14
  }
15
  return solve(0, 0, rods, dp);
16
};
17

18
var solve = function (i, sum, rods, dp) {
19
  if (i == rods.length) {
20
    if (sum == 0) {
21
      return 0;
22
    } else {
23
      return -5000;
24
    }
25
  }
26
  if (dp[i][sum + 5000] != -1) {
27
    return dp[i][sum + 5000];
28
  }
29
  let val = solve(i + 1, sum, rods, dp);
30
  val = Math.max(val, solve(i + 1, sum + rods[i], rods, dp) + rods[i]);
31
  val = Math.max(val, solve(i + 1, sum - rods[i], rods, dp));
32
  dp[i][sum + 5000] = val;
33
  return val;
34
};