思路

线性dp

过程

代码

#include <iostream>
#include <vector>

using namespace std;

const int N = 1e5 + 10;
int a[N], n;

int main()
{
    cin >> n;
    int maxVal = 0;
    for(int i = 0;i < n;i ++)
    {
        cin >> a[i];
        if(a[i] > maxVal) maxVal = a[i];
    }

    vector<int> sum(maxVal + 1);
    vector<int> f = sum, g = sum;

    for(int i = 0;i < n;i ++) sum[a[i]] += a[i];

    for(int i = 1;i <= maxVal;i ++)
    {
        f[i] = g[i - 1] + sum[i];
        g[i] = max(f[i - 1], g[i - 1]);
    }
    cout << max(g[maxVal], f[maxVal]) << endl;

    return 0;
}