Xóa và kiếm điểm trong C++

Mô tả bài toán

Cho mảng nums. Mỗi lần chọn nums[i], nhận nums[i] điểm, và phải xóa tất cả phần tử bằng nums[i]-1 và nums[i]+1. Tìm điểm tối đa.

Ví dụ: [3,4,2] → chọn 4 (được 4 điểm, xóa 3), chọn 2 (được 2 điểm) → tổng 6.

Giải thuật Quy hoạch động (biến thể House Robber)

Vì xóa x-1 và x+1, bài toán tương đương: biến mảng thành tần suất, value[x] = x * freq[x]. Không thể chọn 2 số liền kề. → DP như House Robber trên mảng value.

Cài đặt C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int deleteAndEarn(vector<int>& nums) {
        const int MAX = 10001;
        vector<int> val(MAX, 0);
        for (int x : nums) val[x] += x;
        int take = 0, skip = 0;
        for (int i = 0; i < MAX; i++) {
            int take_i = skip + val[i];
            int skip_i = max(take, skip);
            take = take_i;
            skip = skip_i;
        }
        return max(take, skip);
    }
};

int main() {
    vector<int> v = {3,4,2};
    Solution ob;
    cout << ob.deleteAndEarn(v); // 6
    return 0;
}

Độ phức tạp

• Thời gian: O(n + MAX) (MAX = 10000).
• Không gian: O(MAX).