leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0956.cpp (544B)

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