To solve the problem of finding the maximum sum of non-adjacent elements in an array, we can use a dynamic programming approach with optimized space complexity. Here's the step-by-step solution:

Problem Analysis

The core idea is to make a decision for each element: either include it (and skip the previous element) or exclude it (and keep the maximum sum up to the previous element). This leads to a recurrence relation where each state depends only on the two previous states, allowing us to avoid storing the entire DP array.

Algorithm

1. Initialization: Use two variables (a and b) to track the maximum sum up to the element before the last (a) and the last element (b).
2. Iterate through the array: For each element, compute the new maximum sum by choosing the better option (include current element or exclude it).
3. Update variables: Shift the values of a and b to move forward in the array.

Solution Code

def max_non_adjacent_sum(nums):
    a, b = 0, 0
    for num in nums:
        a, b = b, max(a + num, b)
    return b

Explanation

• Initialization: a and b start at 0 (no elements processed yet).
• For each element:
  • temp = b (store the current b to update a later).
  • b = max(a + num, b): The new b is the maximum of including the current element (a + num) or excluding it (b).
  • a = temp: Update a to the old value of b (sum up to the previous element).
• Result: After processing all elements, b holds the maximum sum of non-adjacent elements.

Complexity

• Time: O(n) (linear pass through the array).
• Space: O(1) (only two variables used, no extra space).

This approach efficiently computes the desired result with optimal time and space complexity. It handles all edge cases (empty array, single element, etc.) correctly. For example:

• nums = [2,7,9,3,1] → returns 12 (sum of 2+9+1).
• nums = [5] → returns 5.
• nums = [] → returns 0.

This is the optimal solution for the problem. ✨

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