设计一个O(n2)时间的算法 找出由n个数组成的序列的最长单调递增子序列。

一、实验目的

1、理解动态规划的基本思想

2、掌握动态规划解决问题的基本步骤，并能进行动态规划算法时间空间复杂度分析。

二、实验内容

设计一个O(n2)时间的算法，找出由n个数组成的序列的最长单调递增子序列。

三、算法描述

1.输入一个序列b[]

2.将该序列进行排序得到新的序列a[](递增的哦）

3.将问题转化为求这两个序列a,b的最大公共子序列

4.运用动态规划的解题思想，先求得子问题的结果，记录在c[][]数组中，

再根据c[][]中的值的情况得到最大公共子序列。

四、程序

#include <iostream>using namespace std;void sortarry(int a[],int number);void LCSLength(int n,int a[],int b[],int c[10][10]);void LCS(int i,int j,int a[],int c[10][10]);int main(){cout<<"How many numbers you want to input?"<<" ";int number=5;cin>>number;int b[number];cout<<"OK,now please input them!"<<endl;for(int i=1;i<=number;i++)cin>>b[i];cout<<"Now you can see the order arry: ";for(int i=1;i<=number;i++)cout<<b[i];cout<<endl;int a[number];for(int i=1;i<=number;i++)a[i]=b[i];sortarry(b,number);cout<<"Now you can see the arry after sort: ";for(int i=1;i<=number;i++)cout<<b[i];cout<<endl;int c[10][10]={0};LCSLength(number,a,b,c);cout<<"Let we see the arry of C:"<<endl;for(int i=1;i<=number;i++){for(int j=1;j<=number;j++)cout<<c[i][j]<<'\t';cout<<endl;}cout<<endl<<"OK,I have founded the longest same arry:"<<endl;LCS(number,number,a,c);}void sortarry(int a[],int number){for(int i=1;i<=number;i++){for(int j=i;j<=number;j++)if(a[i]>a[j]){int temp=a[j];a[j]=a[i];a[i]=temp;}}}void LCSLength(int n,int a[],int b[],int c[10][10]){int i,j;for( i=1;i<n;i++) c[i][0]=0;for( j=1;j<n;j++) c[0][j]=0;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(a[i]==b[j]) {c[i][j]=c[i-1][j-1]+1;}else if(c[i-1][j]>=c[i][j-1]) c[i][j]=c[i-1][j];else c[i][j]=c[i][j-1];}}}void LCS(int i,int j,int a[],int c[10][10]){if(i==0||j==0) return ;if(c[i][j]==c[i-1][j-1]+1){LCS(i-1,j-1,a,c);cout<<a[i];}else if(c[i][j]==c[i-1][j]){LCS(i-1,j,a,c);}elseLCS(i,j-1,a,c);}```![在这里插入图片描述](https://img-/100921175725.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzIxNzkyMQ==,size_16,color_FFFFFF,t_70)