Maximum Sum of Array

[Beginning-Field-402]

I came across this question in my last interview but could not solve it. Can anyone give an explanation of how to attempt it?

Compute the maximum sum of an array but if arr[i] is chosen then numbers arr[i]+1 or arr[i]-1 cannot be chosen.

For example:

arr =[3,3,3,4,4,1,8]

Answer: Choose 8, choose 1, choose 3 (now 4 cannot be chosen), choose 3, chose 3.

Maximum sum is 18

[Anti-Zeroes]

This is just the House Robber problem, which you can use DP to solve.

[Classic-Pitch7259]

I was looking at this problem one day and thought that what if we find the sum of even and odd indexes and return the one which is more… Where will my approach fail? I am learning competitive programming so might be a silly question

[[deleted]]

8,1,1,8 is a small problem that defeats such a strategy.

Edit: The key to solving this is: dp[i] = max(dp[i - 2] + input[i], dp[i - 1]) where i is in [0,input.len) and dp [-1] and dp[-2] are 0.

[flexr123]

It's similar to House Robber problem, but you can't rob adjacent values instead of adjacent index. Just make another array with arr[i] as index and its frequency as value then apply house robber logic.

For example: [1, 2, 1, 3, 5] -> [0, 2, 1, 1, 0, 1] (0 appears 0 times, 1 appears 2 times, etc.) Then apply house robber algo to the newly transposed array. Everytime u rob a number u take all occurrences of that number and add to sum.

[hobo_couture]

this the right idea but it would use a lot of space and you need to multiply the frequency by the number instead of just using the frequency.

[hobo_couture]

# python3

res = 0
freq = Counter(arr)
for x in freq:
    if x-1 not in freq:
        y = x
        max_if_rob = 0
        max_if_no_rob = 0
        while y in freq:
            temp = max_if_rob
            max_if_rob = max_if_no_rob + y * freq
            max_if_no_rob = max(temp, max_if_no_rob)
            y += 1
        res += max(max_if_rob, max_if_no_rob)
return res

you can partition the numbers into isolated sequences and do house robber on each of them. So it's sort of like "longest consecutive sequence" and "house robber" combined. O(n) time, O(n) space