求最长不下降子序列,用c++编程

下面是一个简单的动态规划实现，可以求出最长不下降子序列的长度。具体实现过程如下：

1. 定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长不下降子序列的长度。

2. 初始化 dp 数组，将每个元素的最长不下降子序列长度都初始化为 1。

3. 从第 2 个元素开始遍历数组，对于每个元素 i，将它前面所有不大于它的元素 j 的 dp[j] 值加 1，得到 dp[i] 的值。

4. 遍历 dp 数组，找到其中最大的值，即为最长不下降子序列的长度。

下面是代码实现：

#include <stdio.h>

int main()
{
    int n, i, j, max_len = 1;
    int a[100], dp[100];

    // 输入数组长度和元素值
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    // 初始化 dp 数组
    for (i = 0; i < n; i++) {
        dp[i] = 1;
    }

    // 动态规划求解最长不下降子序列长度
    for (i = 1; i < n; i++) {
        for (j = 0; j < i; j++) {
            if (a[i] >= a[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > max_len) {
            max_len = dp[i];
        }
    }

    // 输出最长不下降子序列长度
    printf("%d", max_len);

    return 0;
}