C++ 解法, 执行用时: 21ms, 内存消耗: 3260KB, 提交时间: 2022-03-27

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return int整型
     */
    int boredom(vector<int>& a) {
        // write code here
        int hash[10005] = {0};
        int dp[10005] = {0};
        //hash表
        //先记录每个元素出现的次数
        for(int i = 0; i < a.size(); i++) hash[a[i]]++;
        //然后就是动态规划问题
        dp[1] = hash[1] * 1;
        for(int i = 2; i <= 10000; i++){
            //不选当前元素  和考虑选当前元素
            dp[i] = max(dp[i - 1], i * hash[i] + dp[i - 2]);
        }
        return dp[10000];
    }
};

C++ 解法, 执行用时: 21ms, 内存消耗: 3264KB, 提交时间: 2022-04-21

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param a int整型vector 
     * @return int整型
     */
    int boredom(vector<int>& a) {
        // write code here
        const int n = *max_element(a.begin(), a.end()) + 1;
        vector<int> dp(n);
        
        for (int i=0; i<a.size(); ++i) {
            dp[a[i]] += a[i];
        }
        
        for (int i=2; i<n; ++i) {
            dp[i] = max(dp[i-1], dp[i] + dp[i-2]);
        }
        
        return dp[n-1];
    }
};

C++ 解法, 执行用时: 22ms, 内存消耗: 3284KB, 提交时间: 2022-06-14

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param a int整型vector
     * @return int整型
     */
    int boredom(vector<int>& a) {
        // write code here
        const int n = *max_element(a.begin(), a.end()) + 1;
        vector<int> dp(n);
         
        for (int i=0; i<a.size(); ++i) {
            dp[a[i]] += a[i];
        }
         
        for (int i=2; i<n; ++i) {
            dp[i] = max(dp[i-1], dp[i] + dp[i-2]);
        }
         
        return dp[n-1];
    }
};

C 解法, 执行用时: 23ms, 内存消耗: 3016KB, 提交时间: 2022-06-25

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param a int整型一维数组 
 * @param aLen int a数组长度
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int max(int a, int b) {
    return a > b ? a : b;
}

int boredom(int* a, int aLen ) {
    int score[10001] = { 0 };
    for (int i = 0; i < aLen; i++) {
        score[a[i]] += a[i];
    }
    
    int dp[10001] = { 0 };
    dp[1] = score[1];
    for (int i = 2; i < 10001; i++) {
        dp[i] = max(score[i] + dp[i-2], dp[i-1]); 
    }
    
    return dp[10000];
}

C 解法, 执行用时: 23ms, 内存消耗: 3140KB, 提交时间: 2022-06-15

#include<math.h>
int max(int i, int j) {
    return i > j ? i : j;
}
int boredom(int* a, int aLen ) {
    int m[10005] = {0};
    int n[10005] = {0};
    for (int i = 0; i < aLen; i++)
        m[*(a + i)]++;
    n[1] = m[1] * 1;
    for (int i = 2; i <= 10000; i++) {
        n[i] = max(n[i - 1], i * m[i] + n[i - 2]);
    }
    return n[10000];
}