leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0956.cpp (544B)

      1 class Solution {
      2   public:
      3     int tallestBillboard(const vector<int> &rods) {
      4         int sum = accumulate(rods.begin(), rods.end(), 0);
      5         vector<int> dp(sum + 1, -1);
      6         dp[0] = 0;
      7 
      8         for (int rod : rods) {
      9             vector<int> dpc = dp;
     10             for (int i = 0; i <= sum - rod; i++) {
     11                 if (dpc[i] < 0) continue;
     12                 dp[i + rod] = max(dp[i + rod], dpc[i]);
     13                 dp[abs(i - rod)] = max(dp[abs(i - rod)], dpc[i] + min(i, rod));
     14             }
     15         }
     16         return dp[0];
     17     }
     18 };