Given an array of integers, find the subset of non-adjacent elements with the maximum sum. Calculate the sum of that subset. It is possible that the maximum sum is , the case when all elements are negative.
For example, given an array we have the following possible subsets. These exclude the empty subset and single element subsets which are also valid.