求无相邻元素的最大和序列实现方案

Got it, let's fix this—your existing code calculates the maximum sum perfectly, but to get the actual elements that make up that sum, we need to track the path we took to reach that maximum, not just the numerical value. Here's how to adjust your approach:

The Core Idea #

Your original algorithm uses two variables (incl and excl) to track the maximum sum including or excluding the current element. We'll extend this by adding two lists to track the actual element sequences that correspond to those sums.

Modified Java Code #

import java.util.ArrayList;
import java.util.List;

public class MaxNonAdjacentSumSequence {
    public static List<Integer> getMaxSumSequence(int[] arr) {
        // Handle edge cases first
        if (arr == null || arr.length == 0) {
            return new ArrayList<>();
        }
        if (arr.length == 1) {
            List<Integer> singleElement = new ArrayList<>();
            singleElement.add(arr[0]);
            return singleElement;
        }

        // Initialize sequences:
        // inclList = sequence including the first element
        List<Integer> inclList = new ArrayList<>();
        inclList.add(arr[0]);
        // exclList = sequence excluding the first element (empty)
        List<Integer> exclList = new ArrayList<>();

        int incl = arr[0];
        int excl = 0;

        for (int i = 1; i < arr.length; i++) {
            int currentNum = arr[i];
            // Check if adding current number to excl's sum gives a better result
            if (excl + currentNum > incl) {
                // Create new sequence for incl: excl's sequence + current number
                List<Integer> newInclList = new ArrayList<>(exclList);
                newInclList.add(currentNum);
                
                // Update excl to be the old incl (since we can't include adjacent elements)
                excl = incl;
                exclList = new ArrayList<>(inclList);
                
                // Update incl to the new sum and sequence
                incl = excl + currentNum;
                inclList = newInclList;
            } else {
                // Keep the existing incl sequence as better
                // Update excl to be the old incl (since we can't include adjacent elements)
                excl = incl;
                exclList = new ArrayList<>(inclList);
                // incl stays the same, so no change to inclList
            }
        }

        // Return the sequence with the larger sum
        return incl > excl ? inclList : exclList;
    }

    public static void main(String[] args) {
        // Test your examples
        int[] test1 = {3, 2, 7, 10};
        System.out.println(getMaxSumSequence(test1)); // Output: [3, 10]

        int[] test2 = {3, 2, 5, 10, 7};
        System.out.println(getMaxSumSequence(test2)); // Output: [3, 5, 7]

        int[] test3 = {5, 5, 10, 100, 10, 5};
        System.out.println(getMaxSumSequence(test3)); // Output: [5, 100, 5]

        int[] test4 = {1, 20, 3};
        System.out.println(getMaxSumSequence(test4)); // Output: [20]
    }
}

How It Works #

• Tracking Sequences: inclList always holds the sequence that gives the maximum sum including the current element, while exclList holds the sequence for excluding the current element.
• Iteration Logic: For each element, we decide if adding it to the excl sequence gives a better sum than keeping the existing incl sequence. If yes, we update our sequences accordingly; if not, we carry forward the existing best sequence.
• Edge Cases: We handle empty arrays and single-element arrays upfront to avoid errors.

Notes #

• If there are multiple sequences with the same maximum sum, this code will return the first one it encounters (left-to-right). If you need to handle ties differently, you'd need to add extra logic to track all possible sequences.

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