Max Subset Sum Not Adjacent

Max Subset Sum not Adjacent

The provided solution aims to find the maximum sum of a subset of non-adjacent elements from a given array.

Problem

Given an array of integers, the goal is to find the maximum possible sum of a subset of elements where no two elements are adjacent to each other in the array.

Approach

The solution utilizes dynamic programming to iteratively compute the maximum sum of non-adjacent elements ending at each position in the array.

# O(n) time | O(n) space
def max_subset_sum_no_adjacent(array):
	if not len(array):
		return
	elif len(array) ==1:
		return array[0]
	maxSums =array[:]
	maxSums[1] = max(array[0], array[1])
	for i in range(2, len(array)):
		maxSums[i] = max(maxSums[i-1], maxSums[i-2]+array[i])
	return maxSums[-1]
	
print(f"max_subset_sum_no_adjacent :: {max_subset_sum_no_adjacent([7,10,12,7,9,14])}")

It maintains an auxiliary array maxSums to store the maximum sum of non-adjacent elements up to the current index.

The first two elements of maxSums are initialized to the first and second elements of the input array, respectively, as they are the base cases.

Then, for each subsequent element in the input array starting from index 2, the maximum sum of non-adjacent elements ending at the current index i is computed as the maximum of either:

•  The maximum sum of non-adjacent elements ending at the previous index i-1 (i.e., maxSums[i-1]).
•  The maximum sum of non-adjacent elements ending at the index two positions back plus the current element (i.e., maxSums[i-2] + array[i]).
•  The last element of the maxSums array represents the maximum sum of non-adjacent elements possible in the entire array.

Time Complexity

• The solution traverses the input array once, computing the maximum sum for each element.
• Therefore, the time complexity is O(n), where n is the length of the input array.

Space Complexity

• The solution uses an auxiliary array maxSums of the same length as the input array to store the maximum sums of non-adjacent elements.
• Therefore, the space complexity is O(n), where n is the length of the input array.

I will now proceed to optimize the solution above to achieve O(1) space complexity as follows:

# O(n) time | O(1) space	
def max_subject_sum_no_adjacent(array):
	if not len(array):
		return
	elif len(array) ==1:
		return array[0]
	second =array[0]
	first =max(array[0], array[1])
	
	for i in range(2, len(array)):
		current = max(first, second + array[i])
		second  = first
		first 	= current
	return first

print(f"max_subject_sum_no_adjacent :: {max_subject_sum_no_adjacent([7,10,12,7,9,14])}")

Unit Tests

Here are some unit tests using Python's unittest module to test the robustness and correctness of the max_subset_sum_no_adjacent function:

import unittest


class TestMaxSubsetSumNoAdjacent(unittest.TestCase):
    def test_example_1(self):
        # Test with the example provided in the prompt
        self.assertEqual(max_subset_sum_no_adjacent([3, 7, 4, 6, 5]), 13)

    def test_empty_array(self):
        # Test with an empty array
        self.assertIsNone(max_subset_sum_no_adjacent([]))

    def test_single_element_array(self):
        # Test with an array containing a single element
        self.assertEqual(max_subset_sum_no_adjacent([5]), 5)

    def test_two_elements_array(self):
        # Test with an array containing two elements
        self.assertEqual(max_subset_sum_no_adjacent([3, 7]), 7)

    def test_all_negative_elements(self):
        # Test with an array containing all negative elements
        self.assertEqual(max_subset_sum_no_adjacent([-2, -3, -1, -5, -4]), -2)

    def test_all_positive_elements(self):
        # Test with an array containing all positive elements
        self.assertEqual(max_subset_sum_no_adjacent([2, 3, 1, 5, 4]), 8)

    def test_mixed_elements(self):
        # Test with an array containing both positive and negative elements
        self.assertEqual(max_subset_sum_no_adjacent([2, -3, 5, -1, 6, -7, 8]), 21)


if __name__ == '__main__':
    unittest.main()

These unit tests cover various scenarios:

•     Testing with the example provided in the prompt.
•     Testing with an empty array.
•     Testing with arrays containing different numbers of elements.
•     Testing with arrays containing all positive elements, all negative elements, and mixed elements.

Each test case asserts whether the max_subset_sum_no_adjacent function returns the expected result for a given input array. These tests help ensure the correctness and robustness of the function implementation.