题解 | 删除相邻数字的最大分数

#include <vector>
#include <algorithm>

class Solution
{
public:
    int boredom(vector<int>& a)
    {
        // 边界处理：空数组直接返回0
        if(a.empty()) return 0;
        
        // 1. 找到数组中的最大值，用于确定统计数组的大小
        int max_value = *max_element(a.begin(), a.end());
        // 2. 统计每个值的总贡献（值 × 出现次数）
        // 例如：数组中有4个2，则count[2] = 2×4 = 8
        vector<int> count(max_value + 1, 0);  // 大小为max_value+1，初始化为0
        for(auto & x : a)
            count[x] += x;  // 累加每个值的总贡献

        // 3. 动态规划计算最大分数
        int n = count.size();  // count的大小是max_value + 1
        vector<int> dp(n);     // dp[i]表示处理到值i时的最大分数
        
        // 初始化dp[0]：值0的总贡献（如果数组中没有0，count[0]就是0）
        dp[0] = count[0];
        // 初始化dp[1]：值1的总贡献与值0的总贡献的较大者
        dp[1] = max(count[0], count[1]);

        // 从值2开始处理，直到最大值
        for(int i = 2; i < n; i++)
        {
            // 状态转移：
            // - 不选值i：最大分数继承dp[i-1]
            // - 选值i：最大分数 = dp[i-2]（前一个不相邻的值的最大分数） + count[i]（当前值的总贡献）
            dp[i] = max(dp[i - 1], dp[i - 2] + count[i]);
        }

        // 返回处理到最大值时的最大分数
        return dp[n - 1];
    }
};