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

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

long long maxPoints(vector<int>& nums) {
    // 统计每个数字出现的次数
    unordered_map<int, long long> count;
    for(int num : nums) {
        count[num]++;
    }
    
    // 找到最大的数字
    int maxNum = 0;
    for(int num : nums) {
        maxNum = max(maxNum, num);
    }
    
    // dp[i]表示考虑到数字i时能获得的最大分数
    vector<long long> dp(maxNum + 2, 0);
    dp[1] = count[1];
    
    // 从小到大计算每个数字的最大分数
    for(int i = 2; i <= maxNum; i++) {
        dp[i] = max(dp[i-1], dp[i-2] + i * count[i]);
    }
    
    return dp[maxNum];
}

int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    for(int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    cout << maxPoints(nums) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static long maxPoints(int[] nums) {
        // 统计每个数字出现的次数
        Map<Integer, Long> count = new HashMap<>();
        int maxNum = 0;
        for(int num : nums) {
            count.put(num, count.getOrDefault(num, 0L) + 1);
            maxNum = Math.max(maxNum, num);
        }
        
        // dp[i]表示考虑到数字i时能获得的最大分数
        long[] dp = new long[maxNum + 2];
        dp[1] = count.getOrDefault(1, 0L);
        
        // 从小到大计算每个数字的最大分数
        for(int i = 2; i <= maxNum; i++) {
            dp[i] = Math.max(dp[i-1], 
                            dp[i-2] + i * count.getOrDefault(i, 0L));
        }
        
        return dp[maxNum];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] nums = new int[n];
        for(int i = 0; i < n; i++) {
            nums[i] = sc.nextInt();
        }
        System.out.println(maxPoints(nums));
        sc.close();
    }
}

def max_points(nums):
    # 统计每个数字出现的次数
    count = {}
    for num in nums:
        count[num] = count.get(num, 0) + 1
    
    # 找到最大的数字
    max_num = max(nums)
    
    # dp[i]表示考虑到数字i时能获得的最大分数
    dp = [0] * (max_num + 2)
    dp[1] = count.get(1, 0)
    
    # 从小到大计算每个数字的最大分数
    for i in range(2, max_num + 1):
        dp[i] = max(dp[i-1], dp[i-2] + i * count.get(i, 0))
    
    return dp[max_num]

n = int(input())
nums = list(map(int, input().split()))
print(max_points(nums))