Let f[i] be the maximum sum he can get from taking only values less than or equal i. Then clearly f[0] = 0 since he can't take any of the aray elements. For other values of i, there are two possible cases. The first case is that he does not take any values from the array that are equal to i (sometimes it is better to not take them so he doesn't have to delete all occurrences of i+1 and i-1). In this case, f[i] = f[i-1]. If he doesn't take any values equal to i, the maximum sum he gets is no different than the maximum sum when he was only allowed to take values up to i-1. The other case is that he does take all occurrences of the value i (it's never optimal to take some but not all occurrences since he has to delete the other elements either way). In this case, he is not allowed to take any occurrences of i-1 since he has to delete them all, but he does get the benefit of adding i * freq[i] to his score (where freq[i] is the number of occurrences of i in the array). The fact that he has to delete all occurrences of i+1 will be taken care of when calculating f[i] so you don't have to worry about that. So in this case f[i] = i * freq[i] + f[i-2]. So when figuring out f[i], you take whichever of these cases results in a higher result. Here is some pseudo-code (assuming you pre-computed freq[i] for all i up to 100,000):

f[0] = 0;
for(int i = 1; i<=100000; i++)
{
f[i] = f[i-1];
if(i > 1) f[i] = Math.max(f[i], f[i-2] + i*freq[i]); // Watch out for overflow here.
}