aboutsummaryrefslogtreecommitdiff
path: root/tallest_billboard.cpp
blob: 1201823c85ad0fd0a7c3eed6c5b4a57e6c2ddfa7 (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
#include "leetcode.h"

class Solution {
public:
  int tallestBillboard(vector<int> &rods) {
    unordered_map<int, int> dp;
    dp[0] = 0;
    for (int i : rods) {
      unordered_map<int, int> tmp;
      for (auto &it : dp) {
        int diff = it.first;
        tmp[diff + i] = max(tmp[diff + i], dp[diff] + i);
        tmp[diff - i] = max(tmp[diff - i], dp[diff]);
      }
      dp.clear();
      dp.insert(tmp.begin(), tmp.end());
    }
    return dp[0];
  }
};

int main() {
  Solution obj;
  vector<int> rods = {1, 2, 3, 6};
  cout << obj.tallestBillboard(rods);
}