如何获取数组不相邻元素最大和对应的元素及索引

Great question! I’ve struggled with this exact problem too—calculating the maximum sum is straightforward with dynamic programming, but figuring out which elements actually contribute to that sum (especially for large arrays) requires a bit of extra tracking. Let’s break this down step by step.

First: Recap the Base DP Approach #

Before we dive into tracking elements, let’s quickly recap the core DP logic for the maximum non-adjacent sum. We typically use two variables:

• incl: The maximum sum we can get including the current element.
• excl: The maximum sum we can get excluding the current element.

For each element in the array:

• New incl = excl + current element (since we can’t include the previous element)
• New excl = max(old incl, old excl) (we take the best sum from either including or excluding the previous element)

The final maximum sum is max(incl, excl). But this doesn’t tell us which elements were chosen.

Method 1: Track Selections with a DP Array (Easy to Understand) #

For smaller to medium arrays, we can use a full DP array plus a boolean array to track whether each element was selected. Here’s how:

Step 1: Build the DP & Selection Arrays #

Let’s define:

• dp[i]: The maximum sum for the first i+1 elements (from index 0 to i).
• selected[i]: A boolean flag indicating if the element at index i is part of the maximum sum.

State Transitions:
For each index i starting from 1:

• If dp[i-1] > dp[i-2] + arr[i]: We don’t select arr[i], so dp[i] = dp[i-1] and selected[i] = false.
• Else: We select arr[i], so dp[i] = dp[i-2] + arr[i] and selected[i] = true.

For the base cases:

• dp[0] = arr[0], selected[0] = true
• dp[1] = max(arr[0], arr[1]), selected[1] = (arr[1] > arr[0])

Step 2: Backtrack to Collect Elements & Indices #

Once we have the selected array, we start from the last index and work backwards:

1. Initialize i = len(arr) - 1
2. Create empty lists to store selected elements and indices.
3. While i >= 0:
   • If selected[i] is true:
     • Add arr[i] to your elements list and i to your indices list.
     • Jump back 2 indices (i -= 2) since we can’t select the adjacent element.
   • Else:
     • Jump back 1 index (i -= 1)
4. Reverse both lists to get the elements in the original order (since we collected them from the end).

Example with your array [2,5,10,1,10]:

• dp array becomes [2,5,12,12,22]
• selected array becomes [true, false, true, false, true]
• Backtracking gives us indices 4,2,0 → reversed to 0,2,4 and elements 2,10,10.

Method 2: Space-Optimized Tracking (For Large Arrays) #

If you’re working with very large arrays (think 100k+ elements), storing a full DP and selected array might be unnecessary. We can optimize space by first calculating the maximum sum, then backtracking without storing the entire DP array.

Step 1: Calculate the Maximum Sum (With State History) #

Instead of just tracking incl and excl, we’ll keep a history of these values as we iterate through the array. We can store them in two separate lists (incl_history and excl_history) where each entry corresponds to the incl/excl value at that index.

Step 2: Backtrack Using the History #

1. Start with current_sum = max(incl_history[-1], excl_history[-1]) and i = len(arr) - 1.
2. Create empty lists for elements and indices.
3. While i >= 0:
   • If i == 0:
     • If arr[i] == current_sum: add it to your lists, break.
     • Else: break.
   • Check if incl_history[i] == current_sum:
     • If yes: this element was selected. Add it to your lists, subtract arr[i] from current_sum, and jump back 2 indices (i -=2).
     • If no: this element wasn’t selected. Jump back 1 index (i -=1), and set current_sum = excl_history[i].

This approach uses O(n) space for the history lists, which is still manageable for large arrays, but you could even optimize further by tracking only the necessary previous states during backtracking (though that gets a bit trickier).

Example Code (Python) #

Here’s a quick implementation of the space-optimized method for your example:

def find_max_non_adjacent_elements(arr):
    n = len(arr)
    if n == 0:
        return [], []
    if n == 1:
        return [arr[0]], [0]
    
    incl_history = [0]*n
    excl_history = [0]*n
    
    incl_history[0] = arr[0]
    excl_history[0] = 0
    
    for i in range(1, n):
        incl_history[i] = excl_history[i-1] + arr[i]
        excl_history[i] = max(incl_history[i-1], excl_history[i-1])
    
    max_sum = max(incl_history[-1], excl_history[-1])
    current_sum = max_sum
    elements = []
    indices = []
    i = n-1
    
    while i >=0:
        if i ==0:
            if arr[i] == current_sum:
                elements.append(arr[i])
                indices.append(i)
            break
        if incl_history[i] == current_sum:
            elements.append(arr[i])
            indices.append(i)
            current_sum -= arr[i]
            i -=2
        else:
            current_sum = excl_history[i]
            i -=1
    
    # Reverse to get original order
    elements.reverse()
    indices.reverse()
    return elements, indices

# Test with your array
arr = [2,5,10,1,10]
elements, indices = find_max_non_adjacent_elements(arr)
print(f"Selected elements: {elements}")  # Output: [2, 10, 10]
print(f"Selected indices: {indices}")    # Output: [0, 2, 4]

Key Notes for Large Arrays #

• Time Complexity: Both methods run in O(n) time—linear time is optimal for this problem, even for huge arrays.
• Space Complexity: The space-optimized method uses O(n) space for the history lists. If you need even more space savings, you can track back by re-calculating the DP states on the fly during backtracking (but this doubles the time to O(2n), which is still acceptable in most cases).
• Edge Cases: Don’t forget to handle arrays of length 0, 1, or arrays with all negative numbers (in that case, you’d select the least negative element).

内容的提问来源于stack exchange，提问作者uday singh