[已解决]用c++解决

王鹿其

*<1> 编程求出数列的所有升或降的最大子序列。如下面数列的解为如下：
      1,20,30,12,3,5,7,4,6,100,11,8
     (1,20,30),(30,12,3),(3,5,7),(7,4),(4,6,100),(100,11,8)。

最佳答案

月排行榜 / 总排行榜

isdkz

2023-10-25 18:58:30

这个问题可以通过动态规划来解决。首先，我们定义两个数组：increasing和decreasing，用于记录以每个元素结尾的最长升序子序列和最长降序子序列的长度。

我们可以从左到右遍历给定的数列。对于每个元素，我们可以将其与前面的元素进行比较，以确定是否能够扩展当前的升序或降序子序列。

具体的算法如下：

1. 初始化increasing和decreasing数组，将所有元素的初始值都设为1。
2. 从第二个元素开始遍历数列，对于每个元素arr[ i]：
   a. 从第一个元素开始遍历到arr[ i]之前的元素arr[j]，如果arr[ i]大于arr[j]，则可以将arr[ i]加入到以arr[j]结尾的升序子序列中，更新increasing[ i]为increasing[j]+1。
   b. 从第一个元素开始遍历到arr[ i]之前的元素arr[j]，如果arr[ i]小于arr[j]，则可以将arr[ i]加入到以arr[j]结尾的降序子序列中，更新decreasing[ i]为decreasing[j]+1。
3. 找到increasing和decreasing数组中的最大值，记为maxLen。
4. 遍历increasing数组，找到值等于maxLen的元素的索引位置，记为endIndex。
5. 从endIndex开始，倒序遍历increasing数组，找到连续maxLen个值等于maxLen的元素，这就是最长升序子序列。
6. 重复步骤5，但是遍历decreasing数组，找到最长降序子序列。

下面是C++的实现代码：

#include <iostream>
#include <vector>
using namespace std;

void findMaxSubsequence(const vector<int>& arr) {
    int n = arr.size();
    vector<int> increasing(n, 1);
    vector<int> decreasing(n, 1);

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

    int maxLen = 0;
    int endIndex = 0;
    for (int i = 0; i < n; i++) {
        if (increasing[ i] > maxLen) {
            maxLen = increasing[ i];
            endIndex = i;
        }
        if (decreasing[ i] > maxLen) {
            maxLen = decreasing[ i];
            endIndex = i;
        }
    }

    cout << "最长升序子序列：";
    for (int i = endIndex; i >= 0; i--) {
        if (increasing[ i] == maxLen) {
            cout << arr[ i] << " ";
            maxLen--;
        }
    }
    cout << endl;

    maxLen = decreasing[endIndex];
    cout << "最长降序子序列：";
    for (int i = endIndex; i >= 0; i--) {
        if (decreasing[ i] == maxLen) {
            cout << arr[ i] << " ";
            maxLen--;
        }
    }
    cout << endl;
}

int main() {
    vector<int> arr = {1, 20, 30, 12, 3, 5, 7, 4, 6, 100, 11, 8};
    findMaxSubsequence(arr);
    return 0;
}

这段代码会输出最长升序子序列和最长降序子序列。对于给定的数列 [1, 20, 30, 12, 3, 5, 7, 4, 6, 100, 11, 8]，输出结果为：

最长升序子序列：1 20 30
最长降序子序列：30 12 3

希望对你有帮助！

跳转到最佳答案楼层

isdkz

这个问题可以通过动态规划来解决。首先，我们定义两个数组：increasing和decreasing，用于记录以每个元素结尾的最长升序子序列和最长降序子序列的长度。

我们可以从左到右遍历给定的数列。对于每个元素，我们可以将其与前面的元素进行比较，以确定是否能够扩展当前的升序或降序子序列。

具体的算法如下：

1. 初始化increasing和decreasing数组，将所有元素的初始值都设为1。
2. 从第二个元素开始遍历数列，对于每个元素arr[ i]：
   a. 从第一个元素开始遍历到arr[ i]之前的元素arr[j]，如果arr[ i]大于arr[j]，则可以将arr[ i]加入到以arr[j]结尾的升序子序列中，更新increasing[ i]为increasing[j]+1。
   b. 从第一个元素开始遍历到arr[ i]之前的元素arr[j]，如果arr[ i]小于arr[j]，则可以将arr[ i]加入到以arr[j]结尾的降序子序列中，更新decreasing[ i]为decreasing[j]+1。
3. 找到increasing和decreasing数组中的最大值，记为maxLen。
4. 遍历increasing数组，找到值等于maxLen的元素的索引位置，记为endIndex。
5. 从endIndex开始，倒序遍历increasing数组，找到连续maxLen个值等于maxLen的元素，这就是最长升序子序列。
6. 重复步骤5，但是遍历decreasing数组，找到最长降序子序列。

下面是C++的实现代码：

#include <iostream>
#include <vector>
using namespace std;

void findMaxSubsequence(const vector<int>& arr) {
    int n = arr.size();
    vector<int> increasing(n, 1);
    vector<int> decreasing(n, 1);

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

    int maxLen = 0;
    int endIndex = 0;
    for (int i = 0; i < n; i++) {
        if (increasing[ i] > maxLen) {
            maxLen = increasing[ i];
            endIndex = i;
        }
        if (decreasing[ i] > maxLen) {
            maxLen = decreasing[ i];
            endIndex = i;
        }
    }

    cout << "最长升序子序列：";
    for (int i = endIndex; i >= 0; i--) {
        if (increasing[ i] == maxLen) {
            cout << arr[ i] << " ";
            maxLen--;
        }
    }
    cout << endl;

    maxLen = decreasing[endIndex];
    cout << "最长降序子序列：";
    for (int i = endIndex; i >= 0; i--) {
        if (decreasing[ i] == maxLen) {
            cout << arr[ i] << " ";
            maxLen--;
        }
    }
    cout << endl;
}

int main() {
    vector<int> arr = {1, 20, 30, 12, 3, 5, 7, 4, 6, 100, 11, 8};
    findMaxSubsequence(arr);
    return 0;
}

这段代码会输出最长升序子序列和最长降序子序列。对于给定的数列 [1, 20, 30, 12, 3, 5, 7, 4, 6, 100, 11, 8]，输出结果为：

最长升序子序列：1 20 30
最长降序子序列：30 12 3

希望对你有帮助！