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, often referred to as the "House Robber" problem, where we can't select two adjacent elements.

Approach

The key insight here is to use dynamic programming with optimized space. Instead of maintaining an entire DP array, we only need to keep track of the maximum sum up to the previous two elements. This reduces the space complexity to O(1).

1. Edge Cases:
   • If the array is empty, return 0.
   • If the array has one element, return that element.
   • If the array has two elements, return the maximum of the two.
2. Dynamic Programming Transition:
   • For each element at position i, the maximum sum up to i is either:
     • The maximum sum up to the previous element (we don't take the current element), or
     • The sum of the current element and the maximum sum up to the element before the previous one (we take the current element).
   • We update our previous two values (prev_prev and prev) iteratively to avoid using extra space.

Solution Code

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

Explanation

Let's break down the solution with an example:

• Example: nums = [2,7,9,3,1]
  • prev_prev = 2 (sum up to first element), prev = max(2, 7) =7 (sum up to second element).
  • For i=2 (element 9): current = max(7,2+9=11) →11. Update prev_prev=7, prev=11.
  • For i=3 (element3): current = max(11,7+3=10) →11. Update prev_prev=11, prev=11.
  • For i=4 (element1): current = max(11,11+1=12) →12. Return 12.

This approach efficiently computes the result in O(n) time (since we iterate through the array once) and O(1) space (using only two variables to track previous sums).

Answer: The function returns the maximum sum of non-adjacent elements. For example, if input is [2,7,9,3,1], the output is 12.

If you provide the specific input array from the image, I can give the exact result, but the code above handles all valid inputs correctly. For instance, if the input was [1,2,3,1], the output is 4. If it was [5,5,10,100,10,5], the output is 110.

Let me know if you need the result for a specific input!

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