Gợi ý

• Ta có thể thấy nếu chọn phần tử ~a_i~ thì tất cả phần tử trong dãy có giá trị ~a_i-1~ và ~a_i+1~ sẽ bị xóa đi, thế nên việc chọn một hay nhiều phần tử có giá trị ~a_i~ đều như nhau. Để tối ưu cho bài toán thì khi chọn ~a_i~ thì ta phải chọn tất cả các phần tử có giá trị bằng ~a_i~.
• Gọi ~cnt_i~ là số phần tử có giá trị bằng ~i~.
• Vì ~a_i \le 10^5~ nên ta có mảng quy hoạch động trong đó ~dp_i~ là tổng điểm lớn nhất khi xét đến giá trị ~i~. Khi đó ta có ~2~ trường hợp:
  • Chọn các phần tử có giá trị bằng ~i~ dp[i] = dp[i-2] + cnt[i]*i
  • Không chọn các phần tử có giá trị bằng ~i~ dp[i] = dp[i-1]

Độ phức tạp thuật toán: ~O(N)~.

Code tham khảo

const int N = 1e5 + 5;
const int maxA = 1e5;
int n;
int a[N], cnt[N];
long long dp[N];
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i], cnt[a[i]]++;
    dp[1] = cnt[1];
    for(int i = 2; i <= maxA; i++){
        dp[i] = max(dp[i-1], dp[i-2] + 1LL*cnt[i]*i);
    }
    cout << dp[maxA];
    return 0;
}