思路大概就是把负数放在前面，枚举将哪一个负数放在前面的价值最大

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2005;
int a[N], n, b[N], dp[N];
bool cmp (int x, int y) {
    return x > y;
}
signed main() {
    scanf ("%lld", &n);
    for (int i = 1; i <= n; i++) {
        scanf ("%lld", &a[i]);
    }
    if (n <= 10) {
        sort (a + 1, a + n + 1);
        int ans = -0x3f3f3f3f;
        do {
            int lst = 0;
            for (int i = 1; i <= n; i++) {
                if (a[i] * lst <= 0) {
                    lst += a[i];
                } else {
                    lst = lst;
                }
            }
            ans = max (ans, lst);
        } while (next_permutation (a + 1, a + n + 1));
        cout << ans << endl;
    } else {
        int sum1 = 0, sum2 = 0;
        for (int i = 1; i <= n; i++) {
            if (a[i] > 0) {
                sum1 ++;
            }
            if (a[i] < 0) {
                sum2 ++;
            }
        }
        if (sum1 == n) {
            int maxx = 0;
            for (int i = 1; i <= n; i++) {
                maxx = max (maxx, a[i]);
            }
            cout << maxx << endl;
        } else if (sum2 == n) {
            int sum = 0;
            sort (a + 1, a + n + 1, cmp);
            cout << a[1] << endl;
        } else if (sum1 == 1){
            int ans = 0;
            sort (a + 1, a + n + 1, cmp);
            int p = 0;
            for (int i = 1; i <= n; i++) {
                if (a[i] < 0) {
                    p = a[i];
                    break;
                }
            }
            cout << a[1] + p;
        } else {
            sort (a + 1, a + n + 1);
            if (sum2 == 0) {
                int maxx = -1;
                for (int i = 1; i <= n; i++) {
                    maxx = max (maxx, a[i]);
                }
                cout << maxx << endl;
                return 0;
            }
            if (sum1 == 0) {
                cout << a[n] << endl;
                return 0;
            }
            int cnt = 0;
            for (int i = 1; i < n; i++) {
                if (a[i] > 0) {
                    b[++cnt] = a[i];
                }
            }
            dp[0] = 1;
            for (int i = 1; i <= cnt; i++) {
                for (int j = 3000; j >= b[i]; j--) {
                    dp[j] = max (dp[j], dp[j - b[i]]);
                }
            }
            int ans = -0x3f3f3f3f3f3f3f3f;
            for (int i = 1; i <= sum2; i++) {
                int x = a[i];
                int maxx = 0;
                for (int now = -x; now >= 0; now--) {
                    if (dp[now]) {
                        maxx = now;
                        break;
                    }
                }
                ans = max (ans, maxx + a[n] + a[i]);
            }
            cout << ans;
        }
    }
    return 0;
}