Flip Array

• Time : $O(sum(A) * size(A))$
• Space : $O(sum(A))$

int Solution::solve(const vector<int> &A) {
    int sum = 0, ma = 0;
    for(auto a : A) sum += a;
    vector<long long> dp(sum + 1, INT_MAX);
    dp[0] = 0;
    for(auto a : A) {
        for(int i = sum; i >= a * 2; i--) {
            dp[i] = min(dp[i-2*a] + 1, dp[i]);
        }
    }
    for(int i = sum; i >= 0; i--) {
        if(dp[i] < INT_MAX) return dp[i];
    }
    return -1;
}