To solve this problem, we need to find the maximum sum of non-adjacent elements in an array. This is a classic dynamic programming problem that can be optimized for space efficiency.

Approach

The key insight here is to use dynamic programming with space optimization. Instead of maintaining an array to store the maximum sum up to each element, we only need two variables to keep track of the maximum sum up to the previous element (prev) and the element before the previous one (prev_prev). This reduces the space complexity to O(1).

1. Edge Cases: Handle empty arrays, arrays with one element, and arrays with two elements directly.
2. Initialization: For arrays longer than two elements, initialize prev_prev to the first element and prev to the maximum of the first two elements.
3. Iterate: For each subsequent element, compute the current maximum sum as the maximum of either:
   • Not taking the current element: prev (sum up to the previous element).
   • Taking the current element: prev_prev + current element (sum up to the element before the previous one plus the current element).
4. Update: Update prev_prev and prev for the next iteration.

Solution Code

def max_non_adjacent_sum(arr):
    if not arr:
        return 0
    n = len(arr)
    if n == 1:
        return arr[0]
    prev_prev = arr[0]
    prev = max(arr[0], arr[1])
    for i in range(2, n):
        current = max(prev, prev_prev + arr[i])
        prev_prev, prev = prev, current
    return prev

Explanation

• Edge Cases:
  • Empty array: Return 0.
  • Single element: Return the element itself.
  • Two elements: Return the maximum of the two elements.
• Initialization: prev_prev holds the maximum sum up to the first element, prev holds the maximum sum up to the second element.
• Iteration: For each element from the third onwards, we calculate the current maximum sum by choosing between including the current element (adding to prev_prev) or excluding it (keeping prev).
• Space Optimization: By using only two variables, we avoid the need for an O(n) DP array, making the solution space-efficient.

This approach runs in O(n) time complexity (since we iterate through the array once) and O(1) space complexity, which is optimal for this problem.

Example: For the array [3, 2, 7, 10], the maximum sum is 3 + 10 = 13, which the code correctly computes. For [3, 2, 5, 10,7], the result is 3+5+7=15.

This solution handles all cases, including arrays with negative numbers, by always choosing the optimal sum at each step.

作者声明:本文包含人工智能生成内容。