leetcode

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 };