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
27
28
29

#include <iostream>
#include <vector>

class Solution {
public:
    int tallestBillboard(std::vector<int>& rods) {
        int sum = 0;
        for (int r : rods) {
            sum += r;
        }
        std::vector<int> dp(sum + 1, -1);
        dp[0] = 0;
        
        for (int r : rods) {
            std::vector<int> tmp(dp);
            for (int j = 0; j <= sum; ++j) {
                if (tmp[j] < 0) {
                    continue;
                }
                if (j + r <= sum) {
                    dp[j + r] = std::max(dp[j + r], tmp[j] + r);
                }
                dp[std::abs(j - r)] = std::max(dp[std::abs(j - r)], std::max(tmp[j], tmp[j] - j + r));
            }
        }
        
        return dp[0];
    }
};