Maximum sum subset of array with no adjacent elements in subset

Let’s understand this problem. A non-negative integer array is given as input. We need to find maximum sum which can be possible by adding non-adjacent element of the given array. In hindsight, this may look a bit complex problem to solve. But the final solution will be simple and elegant.

The first magical step to deal with these type of problems is, to try to break the problem into smaller sub-problems. Next, is to identify the pattern in solution of these sub-problems. If there is indeed a pattern, then generalize the solution to achieve the solution to the original problem. This approach is known as Dynamic Programming. Read more about Dynamic programming here.

Let’s come back to our problem. Consider arr = [7, 10, 12, 7, 9, 14] as given array. Consider first the subsets of 1 element. The maximum sum will be the element itself. Next, consider the subsets of 2 elements like {7, 10} -> 10 (largest in two), {10, 12} -> 12 and so on. For 3 element, {7, 10, 12} -> 19, {10, 12, 7} -> 17, {12, 7, 9} -> 21 and so on. Given this, can we construct array (say max_sub_arr) which contains maximum sum at each index, till the index in the array. Confusing ? Fair enough. Let’s assume we have array of one element with the value arr[0], then max_sub_arr would be [7]. Now, apply same for two element then max_sub_arr = [7, 10]. Repeat for elements up to arr[2] then, max_sub_arr = [7, 10, 19] and so on. Can you identify a pattern ? Try modelling for next index ie [3]. If you calculated it right, max_sub_arr[3] = 19. The pattern is,

element_at_index_in_max_sub_array = max(arr[i] + max_sub_arr[i-2], max_sub_arr[i-1])

If you are constructing resultant array like this, value at index can be calculated using value at previous indices of resultant max_sub_array and the original value at index. The value at any index is guranteed to be maximum sum of subsets, as all the previous values at each indices are representing maximum sum till the given index.

Now, for the above array arr, resultant array would be:

max_sub_arr = [7, 10, 19, 19, 28, 33]

and the maximum sum is 33.

Code:

    def max_subset_sum_with_no_adjacent_second(array):
        if not array:
            return 0
        if len(array) == 1:
            return array[0]
        elif len(array) == 2:
            return max(array[0], array[1])
        first, second = array[0], max(array[0], array[1])
        for i, val in enumerate(array[2:], start=2):
            current = max(second, first + val)
            first, second = second, current
        return current

This is optimized version of the algorithm discussed above. Time complexity is O(n), as the algorithm requires traversal of all the element in array once. Space complexity is O(1) . We are not constructing any resultant array here, instead, we are using temporary variables to achieve the solution.

Let me know, if you see any improvement or you know any better way to solve this problem.