秋天到了，轩轩组织大家去游乐园观光，

秋天到了，轩轩组织大家去游乐园观光，山山发现游乐园一共有
10 个娱乐设施（1-10 号娱乐设施离出口的距离依次递减），并且决
定按照排队人数多少来游玩这些娱乐设施，即每次所游玩的娱乐设施
的排队人数都要大于前一个娱乐设施。同时大家还有另一个游玩习
惯，游玩顺序必须离出口从远到近。队员们希望在满足上面条件的同
时，尽可能多的游玩娱乐设施，你能帮他们找出最多可能浏览的景点
数么？（知识点：最大升序子序列）
例：输入（排队人数）：
10 31 22 57 38 66 79 101 83 120
输出：
7

引用皆我百晓生小程序回复内容作答：
思路：
首先我们可以先对输入的排队人数进行排序，以方便后续的处理。
然后我们定义一个数组dp，dp[i]表示以第i个娱乐设施为结束的最大升序子序列的长度。
对于dp数组的填充，我们可以使用动态规划的方法。
从排队人数的第一个设施开始，依次考虑后面的设施。
如果第i个设施的排队人数大于之前的某个设施的排队人数，并且dp[i]小于dp[j]+1，我们就更新dp[i] = dp[j]+1。
在整个过程中，我们记录下最大的dp[i]的值，即为最多可能浏览的景点数。

代码如下：

#include <stdio.h>

int main()
{
    int n = 10;  // 娱乐设施的个数
    int queue[10] = {10, 31, 22, 57, 38, 66, 79, 101, 83, 120};  // 排队人数
    int sortedQueue[10];  // 排序后的排队人数
    int dp[10];  // dp数组，记录以第i个娱乐设施为结束的最大升序子序列的长度
    int maxCount = 0;  // 最多可能浏览的景点数

    // 对排队人数进行排序
    for (int i = 0; i < n; i++) {
        sortedQueue[i] = queue[i];
    }
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++) {
            if (sortedQueue[j] > sortedQueue[j + 1]) {
                int temp = sortedQueue[j];
                sortedQueue[j] = sortedQueue[j + 1];
                sortedQueue[j + 1] = temp;
            }
        }
    }

    // 对dp数组进行填充
    for (int i = 0; i < n; i++) {
        dp[i] = 1;  // 初始化为1
        for (int j = 0; j < i; j++) {
            if (sortedQueue[i] > sortedQueue[j] && dp[i] < dp[j] + 1) {
                dp[i] = dp[j] + 1;
            }
        }
        if (dp[i] > maxCount) {
            maxCount = dp[i];
        }
    }

    printf("%d\n", maxCount);

    return 0;
}

【以下回答由 GPT 生成】

解决方案

步骤 1

首先，我们需要定义一个函数 findMaxVisited 来寻找最多可能浏览的景点数。函数接收一个整数数组作为参数，表示各个景点的排队人数。

int findMaxVisited(int arr[], int n) {

}

步骤 2

接下来，我们创建一个辅助数组 dp，用于存储最长的升序子序列的长度。

int dp[n];

步骤 3

然后，我们遍历输入的排队人数数组，计算出 dp 数组的值。

for(int i = 0; i < n; i++) {
    dp[i] = 1; // 初始化为1，因为每个单独的景点也算一个子序列
    // 比较当前景点和前面所有景点的排队人数，如果满足条件则更新 dp[i]
    for(int j = 0; j < i; j++) {
        if(arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
            dp[i] = dp[j] + 1;
        }
    }
}

步骤 4

最后，我们在 dp 数组中找到最大的值，即为最多可能浏览的景点数。

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

完整代码

int findMaxVisited(int arr[], int n) {
    int dp[n];

    for(int i = 0; i < n; i++) {
        dp[i] = 1; // 初始化为1，因为每个单独的景点也算一个子序列
        // 比较当前景点和前面所有景点的排队人数，如果满足条件则更新 dp[i]
        for(int j = 0; j < i; j++) {
            if(arr[i] > arr[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }

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

    return maxVisited;
}

测试代码

#include <stdio.h>

int main() {
    int arr[] = {10, 31, 22, 57, 38, 66, 79, 101, 83, 120};
    int n = sizeof(arr) / sizeof(arr[0]);

    int maxVisited = findMaxVisited(arr, n);

    printf("%d\n", maxVisited);

    return 0;
}

输出结果

复杂度分析

该解决方案的时间复杂度为 O(N^2)，其中 N 表示景点的数量。因为需要两层循环来计算 dp 数组的值。空间复杂度为 O(N)，用于存储 dp 数组。

【相关推荐】

你可以看下这个问题的回答https://ask.csdn.net/questions/7723967

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^

秋天到了， 轩轩组织大家去游乐园观光，