最长不下降子序列.cpp

来自「这里面是很多经典算法的源代码」· C++ 代码 · 共 78 行

#include<stdio.h>
#include<stdlib.h>
int p[100]={3,18,7,14,10,12,23,41,16,24};
int dp[100];
int next[100];
int n;
int max(int* pp,int n)
{
	int max;
	max=pp[0];
	for(int i=1;i<n;i++)
	{
		if(pp[i]>max)
		{
			max=pp[i];
		}
	}
	return max;
}
int maxij(int* pp,int n)
{
	int max;
	max=0;
	for(int i=1;i<n;i++)
	{
		if(pp[i]>pp[max])
		{
			max=i;
		}
	}
	return max;
}
main()
{
	int i;
	int getlength(int);
	scanf("%d",&n);
	/*for(i=0;i<n;i++)
	{
		scanf("%d",&p[i]);
	}*/
	for(i=n-1;i>=0;i--)
	{
		dp[i]=getlength(i);
	}
	int head=maxij(dp,100);
	do
	{
		printf("%d ",p[head]);
		head=next[head];
	}
	while(head!=0);
	
}
int getlength(int i)
{
	if(dp[i])
	{
		return dp[i];
	}
	int section[100]={0,0};
	if(i==n-1)
	{
		dp[i]=1;
		next[i]=0;
		return dp[i];
	}
	for(int j=i+1;j<n;j++)
	{
		if(p[j]>=p[i])
		{
			section[j]=getlength(j);
		}
	}
	dp[i]=max(section,100)+1;
	next[i]=maxij(section,100);
	return dp[i];
}