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 where we can optimize space by keeping track of only the previous two values instead of the entire array.

Approach

1. Problem Analysis: The key insight is that for each element, we have two choices: either include it in the sum (and skip the previous element) or exclude it (and take the maximum sum up to the previous element).
2. Dynamic Programming Optimization: Instead of maintaining a full DP array, we use two variables (prev_prev and prev) to keep track of the maximum sum up to the element before the previous one and the previous element, respectively.
3. Base 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.
4. Iterate Through the Array: For each element starting from the third one, compute the current maximum sum as the maximum of including the current element (sum of prev_prev and current element) or excluding it (sum of prev).

Solution Code

nums = list(map(int, input().split()))
n = len(nums)

if n == 0:
    print(0)
elif n == 1:
    print(nums[0])
elif n == 2:
    print(max(nums[0], nums[1]))
else:
    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
    print(prev)

Explanation

• Initialization: We start with prev_prev as the first element and prev as the maximum of the first two elements.
• Iteration: For each subsequent element, we calculate the current maximum sum by choosing between including the current element (adding it to prev_prev) or excluding it (keeping prev). We then update prev_prev and prev to move forward in the array.
• Result: The final value of prev gives the maximum sum of non-adjacent elements in the array.

This approach runs in O(n) time complexity and O(1) space complexity, making it efficient for large arrays. The example input [1,2,3,1] returns 4 (sum of 1 and 3), which is correct. Another example [2,7,9,3,1] returns 12 (sum of 2,9,1), which is also correct.

This solution handles all edge cases, including negative numbers, and provides an optimal way to solve the problem.

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