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. ✨

（免责声明：本文为本网站出于传播商业信息之目的进行转载发布，不代表本网站的观点及立场。本文所涉文、图、音视频等资料的一切权利和法律责任归材料提供方所有和承担。本网站对此资讯文字、图片等所有信息的真实性不作任何保证或承诺，亦不构成任何购买、投资等建议，据此操作者风险自担。） 本文为转载内容，授权事宜请联系原著作权人，如有侵权，请联系本网进行删除。