C++如何在数组中找到最长可能的递减数字组合

#include <iostream>
#include <vector>

using namespace std;

vector<int> findLongestDecreasingSubsequence(vector<int>& nums) {
    int n = nums.size();
    vector<int> dp(n, 1); // dp[i]表示以nums[i]结尾的最长递减子序列的长度

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[j] > nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }

    int maxLength = 0;
    int endIndex = 0;
    for (int i = 0; i < n; i++) {
        if (dp[i] > maxLength) {
            maxLength = dp[i];
            endIndex = i;
        }
    }

    vector<int> result;
    while (maxLength > 0) {
        result.insert(result.begin(), nums[endIndex]);
        maxLength--;
        endIndex--;
        while (endIndex >= 0 && dp[endIndex] != maxLength) {
            endIndex--;
        }
    }

    return result;
}

int main() {
    vector<int> nums = {5, 6, 3, 4, 8, 1, 2, 9};
    vector<int> longestDecreasingSubsequence = findLongestDecreasingSubsequence(nums);

    cout << "最长递减子序列为：";
    for (int num : longestDecreasingSubsequence) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}