Maximum Sum of Non-Adjacent Elements

Maximum Sum of Non-Adjacent Elements

January 9, 2024
medium
dynamic programming

Problem #

Given an array of positive integers, find the maximum sum of non-adjacent elements in the array.

Example: #

  1. Input: nums = [3, 2, 7, 10] Output: 13 Explanation: The maximum sum is obtained by taking elements 3 and 10.

  2. Input: nums = [3, 2, 5, 10, 7] Output: 15 Explanation: The maximum sum is obtained by taking elements 3, 5, and 7.

Solution Approach #

This problem can be solved using dynamic programming. The idea is to iterate through the array and at each step, decide whether to include the current element in the sum. The maximum sum at each point is the maximum of two choices: including the current element or excluding it.

Algorithm Steps #

  1. If the array is empty, return 0.
  2. Create two variables, include and exclude, initialized to 0. include represents the maximum sum including the current element, and exclude represents the maximum sum excluding the current element.
  3. Iterate through the array. For each element:
    • Calculate the new include as the maximum of the previous exclude plus the current element and the previous include.
    • Update exclude to be the maximum of the previous include and exclude.
  4. Return the maximum of include and exclude.

Code (Python) # 

def maxSumNonAdjacent(nums):
    if not nums:
        return 0

    include, exclude = 0, 0
    for num in nums:
        new_include = exclude + num
        exclude = max(include, exclude)
        include = new_include

    return max(include, exclude)

# Test the function
print(maxSumNonAdjacent([3, 2, 7, 10]))   # Output: 13
print(maxSumNonAdjacent([3, 2, 5, 10, 7])) # Output: 15

Code Analysis #

Iterating Over the Array:

for num in nums:
    new_include = exclude + num
    exclude = max(include, exclude)
    include = new_include

For each element num in the array nums:

  • new_include calculates the sum of the current element and exclude (which represents the maximum sum excluding the previous element).
  • exclude is updated to be the maximum of the previous include and exclude. This essentially means excluding the current element and taking the maximum sum up to the previous element.
  • include is then updated to new_include.

Return the Maximum Sum:

return max(include, exclude)

After processing all elements, the function returns the maximum of include and exclude. This is the maximum sum of non-adjacent elements in the array.

Time and Space Complexity: #

  • Time Complexity: O(n) - The function iterates through each element in the array once, where n is the number of elements in the array.
  • Space Complexity: O(1) - The solution uses a constant amount of extra space, as it only requires a few variables regardless of the size of the input array.

Time Complexity #

The time complexity is O(n), where n is the number of elements in the array, as we iterate through the array once.

Space Complexity #

The space complexity is O(1), as we only use a constant amount of extra space.