#include <iostream>
using namespace std;
int is_ordered5(int a, int b,int c,int d,int f);
int is_ordered4(int a, int b,int c,int d);
int is_ordered3(int a, int b,int c);
void main()
{
int a[5] ;
int flag1=1,flag2=1;
cout<<"请输入五个不相等的整数：";
for(int m=0;m<5;m++)
cin>>a[m];
int *p;
p=&a[0];
cout<<endl<<"输入的数字中最长升序和降序序列为:"<<endl;
if(is_ordered5(p[0],p[1],p[2],p[3],p[4]))

{
for(int i=0;i<5;i++)
cout<<p[i]<<"\t";

flag1=0;
}
if(flag1==1)
{
for (int i = 0;i < 5;++i)
for (int j = i+1;j < 5;++j)
for (int k = j+1;k < 5;++k)
for(int l=k+1;l<5;l++)
{
if (is_ordered4(a[i],a[j],a[k],a[l]))
{
cout << a[i] <<"\t"<< a[j] <<"\t"<<a[k] <<"\t"<< a[l]<<"\n";
flag2=0;
}
}
if(flag2==1)

{
for (int p = 0;p < 5;++p)
for (int q = p+1;q < 5;++q)
for (int h = q+1;h < 5;++h)
if(is_ordered3(a[p],a[q],a[h]))
cout<<a[p]<<"\t"<<a[q]<<"\t"<<a[h]<<"\n";
}
}
}

int is_ordered5(int a, int b,int c,int d,int f)
{
return(a>b && b>c && c>d && d>f||a<b && b<c && c<d && d<f);
}
int is_ordered4(int a, int b,int c,int d)
{
return(a>b && b>c && c>d ||a<b && b<c && c<d );
}
int is_ordered3(int a, int b,int c)
{
return(a>b && b>c ||a<b && b<c);
}

他已经说的很好了，就是这样，原来最长递增子序列问题可以规约到最长公共子序列问题，我以前到没想过，一直是直接用动态规划求解的。

double post --- due to the problem of the forum. deleted.

[此贴子已经被作者于2007-7-13 3:02:31编辑过]

The LCS (longest common subsequence) algorithm is often an O(n^2) algorithm, as implemented by a dynamic programming technique.

The LMIS (or LIS, or LMS, short for Longest Monotonically Increasing Subsequence) algoritm based on LCS is O(n^2) since LCS itself is. If you use dynamic programming to write the LMIS algorithm, you can achieve O(n lgn) time complexity, by using some binary search technique in the process. That means your hard work is rewarded.