技术问询：实现2的幂整数的最长增减子序列求解函数

Got it, let's break down how to implement this function exactly as you described. We'll use C++ since you mentioned vector and deque from the STL, and walk through each part step by step.

Step 1: Define Required Types & Helper Function #

First, let's set up the enum for direction and a helper to check if a number is a power of two (note: we'll handle 0 and negatives as non-powers of two, since they don't fit the definition):

#include <vector>
#include <deque>
#include <algorithm>
#include <functional>

// Enum to specify subsequence direction
enum class SequenceDirection {
    Increment,
    Decrement
};

// Helper to check if a number is a valid power of two
bool isPowerOfTwo(int n) {
    if (n <= 0) return false;
    // A power of two has exactly one bit set in binary
    return (n & (n - 1)) == 0;
}

Step 2: Core Function Implementation #

The main function does three critical things:

1. Filters the input vector to keep only powers of two
2. Uses dynamic programming to calculate the length of the longest valid subsequence
3. Backtracks through the DP results to collect all possible longest subsequences

Here's the full implementation:

deque<std::vector<int>> findLongestPowerOfTwoSubsequences(const std::vector<int>& input, SequenceDirection dir) {
    // Step 1: Filter out non-powers of two
    std::vector<int> filtered;
    std::copy_if(input.begin(), input.end(), std::back_inserter(filtered), isPowerOfTwo);
    
    // Edge case: no valid elements to process
    if (filtered.empty()) {
        return {};
    }

    int n = filtered.size();
    // DP array: dp[i] = length of longest valid subsequence ending at index i
    std::vector<int> dp(n, 1);
    int maxLength = 1;

    // Step 2: Fill DP array
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            bool meetsDirection = false;
            if (dir == SequenceDirection::Increment) {
                meetsDirection = filtered[i] > filtered[j];
            } else {
                meetsDirection = filtered[i] < filtered[j];
            }

            if (meetsDirection && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                maxLength = std::max(maxLength, dp[i]);
            }
        }
    }

    // Step 3: Backtrack to collect all longest subsequences
    deque<std::vector<int>> result;
    // Recursive helper for backtracking
    std::function<void(int, int, std::vector<int>)> backtrack = [&](int index, int currentLen, std::vector<int> path) {
        path.push_back(filtered[index]);
        if (currentLen == 1) {
            std::reverse(path.begin(), path.end());
            result.push_back(path);
            return;
        }
        // Check all previous elements that can lead to this subsequence
        for (int j = index - 1; j >= 0; --j) {
            bool meetsDirection = false;
            if (dir == SequenceDirection::Increment) {
                meetsDirection = filtered[j] < filtered[index];
            } else {
                meetsDirection = filtered[j] > filtered[index];
            }
            if (dp[j] == currentLen - 1 && meetsDirection) {
                backtrack(j, currentLen - 1, path);
            }
        }
    };

    // Start backtracking from all indices that end a longest subsequence
    for (int i = 0; i < n; ++i) {
        if (dp[i] == maxLength) {
            backtrack(i, maxLength, {});
        }
    }

    return result;
}

Step 3: Key Details Explained #

• Filtering: We first strip out any values that aren't powers of two—they don't contribute to our target subsequences.
• Dynamic Programming: The dp array tracks the longest valid subsequence ending at each position. For every element, we check all prior elements to see if they fit the required direction (increasing/decreasing) and update the DP value if a longer subsequence is found.
• Backtracking: Once we know the maximum subsequence length, we trace back from all elements that terminate a longest subsequence. This ensures we collect every possible valid path that forms a longest subsequence, not just one.

Step 4: Example Usage #

Here's how you might test the function:

#include <iostream>

void printSubsequences(const deque<std::vector<int>>& seqs) {
    std::cout << "Found " << seqs.size() << " longest subsequences:\n";
    for (const auto& seq : seqs) {
        std::cout << "[ ";
        for (int num : seq) {
            std::cout << num << " ";
        }
        std::cout << "]\n";
    }
}

int main() {
    std::vector<int> input = {1, 2, 4, 8, 3, 6, 16, 2, 4};
    
    // Get longest increasing subsequences
    auto incrSeqs = findLongestPowerOfTwoSubsequences(input, SequenceDirection::Increment);
    printSubsequences(incrSeqs);

    std::cout << "\n";

    // Get longest decreasing subsequences
    auto decrSeqs = findLongestPowerOfTwoSubsequences(input, SequenceDirection::Decrement);
    printSubsequences(decrSeqs);

    return 0;
}

Sample Output #

Found 1 longest subsequences:
[ 1 2 4 8 16 ]

Found 2 longest subsequences:
[ 16 4 2 ]
[ 16 8 4 2 ]

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