c语言动态规划

解题思路:

这段代码是用来解决最长不下降子序列（Longest Non-Decreasing Subsequence）的问题。该问题要求找出给定数组中最长的子序列，使得子序列中元素的顺序非严格递增。

让我来逐步解释代码的功能：

maxn 函数定义了一个简单的函数，用来比较两个数的大小，并返回较大的那个数。

在 main 函数中：

首先通过 scanf 读入整数 n，表示接下来要输入的数组长度。

之后定义了三个数组 a[n]、f[n]、g[n]，分别用来存储输入的数组、动态规划过程中计算的值。

接着是第一个循环，用来计算以每个元素结尾的最长不下降子序列长度 f[i]：

对于每个位置 i，初始化 f[i] 为 1。

然后对于位置 i 前面的每个位置 j，如果 a[j] < a[i]，则更新 f[i] 为 f[j]+1 或者保持不变，即 f[i] = maxn(f[i], f[j]+1)。

第二个循环则是倒着计算以每个元素开始的最长不下降子序列长度 g[i]：

对于每个位置 i，初始化 g[i] 为 1。

然后对于位置 i 后面的每个位置 j，如果 a[j] < a[i]，则更新 g[i] 为 g[j]+1 或者保持不变，即 g[i] = maxn(g[i], g[j]+1)。

最后一个循环用来找出整个序列的最长不下降子序列长度：

对于每个位置 i，计算 g[i]+f[i]-1 的最大值，并赋值给 count。

最后输出 count即为所求的最长不下降子序列的长度。

总体来说，这段代码使用了动态规划的思想，通过两次遍历得到以每个位置结尾和开始的最长不下降子序列长度，并找出全局最优的结果。

注意事项:

参考代码:

#include

int maxn(int q,int p){

return q>p?q:p;

}

int main(){

int n;

scanf("%d",&n);

int a[n],f[n],g[n];

for(int i=1;i<=n;i++)

scanf("%d",&a[i]);

for(int i=1;i<=n;i++){

f[i]=1;

for(int j=1;j<i;j++){

if(a[j]<a[i]) f[i]=maxn(f[i],f[j]+1);

}

}

for(int i=n;i;i--){

g[i]=1;

for(int j=n;j>i;j--)

if(a[j]<a[i])g[i]=maxn(g[i],g[j]+1);

}

int count=0;

for(int i=1;i<=n;i++){

count=maxn(count,g[i]+f[i]-1);

}

printf("%d",count);

return 0;

}