程序填空题：求解最长递增子序列问题（动态规划法）
求解最长递增子序列问题。给定一个无序的整数序列a[0..n-1]，求其中最长递增子序列的长度（不一定连续）。
```c++
#include
#include
#define N 100
using namespace std;
void IncreaseOrder(int a[],int dp[],int x[][N],int n)
{
int i, j, k, index;
for (i = 0; i < n; i++) //依次计算a[0]~a[i]的最长递增子序列
{
dp[i] = 1;
x[i][0] = a[i];
int max = 1;
int maxindex=i; //初始化递增子序列长度的最大值
for (j=0; j {
if ((a[j] < a[i]) && (max {
@@[max = dp[j]+1](2);
@@[maxindex=j](2);
}
}
if(maxindex!=i){
dp[i] = max;
for (k = 0; k < max-1; k++) //存储最长递增子序列
x[i][k] = @@[x[maxindex][k]](2);
@@[x[i][max-1]= a[i]](2);
}
}
}
int main()
{
//dp[i]表示a[0..i]中以a[i]结尾的最长递增子序列的长度
//X[i][0..dp[i]-1]表示以a[i]结尾的最长递增子序列
int A[N],dp[N],X[N][N];
int n,i,index;
cin>>n;
for(i=0;i cin>>A[i];
IncreaseOrder(A,dp,X,n);
for (index = 0, i = 1; i < n; i++) //求所有递增子序列的最大长度
if (dp[index] < dp[i])
index = i;
cout<
for (i = 0; i < dp[index]; i++) //输出最长递增子序列
cout< return 0;
}
```
### 输入格式:
第一行为正整数n，表示序列元素个数，第二行依次输入n个数。
```in
9
2 1 5 3 6 4 8 9 7
```
### 输出格式:
输出最长递增子序列的长度及序列。
```out
5
2 5 6 8 9
```
答案：
第1空：max = dp[j]+1
第2空：maxindex=j
第3空：x[maxindex][k]
第4空：x[i][max-1]= a[i]
```c++
#include
#include
#define N 100
using namespace std;
void IncreaseOrder(int a[],int dp[],int x[][N],int n)
{
int i, j, k, index;
for (i = 0; i < n; i++) //依次计算a[0]~a[i]的最长递增子序列
{
dp[i] = 1;
x[i][0] = a[i];
int max = 1;
int maxindex=i; //初始化递增子序列长度的最大值
for (j=0; j
if ((a[j] < a[i]) && (max
@@[max = dp[j]+1](2);
@@[maxindex=j](2);
}
}
if(maxindex!=i){
dp[i] = max;
for (k = 0; k < max-1; k++) //存储最长递增子序列
x[i][k] = @@[x[maxindex][k]](2);
@@[x[i][max-1]= a[i]](2);
}
}
}
int main()
{
//dp[i]表示a[0..i]中以a[i]结尾的最长递增子序列的长度
//X[i][0..dp[i]-1]表示以a[i]结尾的最长递增子序列
int A[N],dp[N],X[N][N];
int n,i,index;
cin>>n;
for(i=0;i
IncreaseOrder(A,dp,X,n);
for (index = 0, i = 1; i < n; i++) //求所有递增子序列的最大长度
if (dp[index] < dp[i])
index = i;
cout<
for (i = 0; i < dp[index]; i++) //输出最长递增子序列
cout<
}
```
### 输入格式:
第一行为正整数n，表示序列元素个数，第二行依次输入n个数。
```in
9
2 1 5 3 6 4 8 9 7
```
### 输出格式:
输出最长递增子序列的长度及序列。
```out
5
2 5 6 8 9
```
答案：
第1空：max = dp[j]+1
第2空：maxindex=j
第3空：x[maxindex][k]
第4空：x[i][max-1]= a[i]
