To solve this problem, we need to find the maximum sum of non-adjacent elements in an array of non-negative integers. This is a classic dynamic programming problem, often referred to as the "House Robber" problem, where we avoid picking adjacent elements to maximize the sum.
Approach
The key insight here is to use dynamic programming with constant space optimization. Instead of maintaining an entire DP array, we only keep track of the last two maximum sums:
- prev_prev: The maximum sum up to the element before the previous one.
- prev: The maximum sum up to the previous element.
For each current element:
- If we pick the current element, the sum is
prev_prev + current_element(since we can't pick the previous element). - If we don't pick the current element, the sum remains
prev. - The maximum of these two values becomes the new
prev, and the oldprevbecomes the newprev_prev.
Solution Code
def max_non_adjacent_sum(nums):
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
a = nums[0]
b = max(nums[0], nums[1])
for i in range(2, n):
c = max(b, a + nums[i])
a, b = b, c
return b
Explanation
- Edge Cases:
- If the array is empty, return
0. - If the array has only one element, return that element.
- If the array is empty, return
- Initialization:
a(prev_prev) is set to the first element.b(prev) is set to the maximum of the first two elements.
- Iterate:
- For each element from the third one onwards, compute the maximum sum (
c) by either taking the current element (adding toa) or skipping it (keepingb). - Update
aandbto move forward in the array.
- For each element from the third one onwards, compute the maximum sum (
- Result: The value
bat the end of the iteration gives the maximum sum of non-adjacent elements.
This approach runs in O(n) time (since we iterate through the array once) and uses O(1) space (only two variables to track previous sums), making it optimal for large arrays.
Example: For the array [2,7,9,3,1], the result is 12 (2+9+1). For [1,2,3,1], the result is 4 (1+3). Both are correctly handled by the code.
The final answer is the function max_non_adjacent_sum which returns the desired maximum sum. For the given problem (assuming the input array is as per the classic example), the output would be the result of this function applied to the input array.
If we assume the input array is, say, [2,7,9,3,1], the answer is 12. However, since the input image isn't visible, the general solution is as provided above. For any valid input array, the function will compute the correct maximum sum.
Let's assume the input array here is the common example [2,7,9,3,1], so the answer is:
12


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