算法设计作业LIS(最长递增子序列)

/*
功能说明: 给定一个非负整数数组,找出最长递增子序列.
作者:hfjiang
完成日期: 2005-3-13
*/
#include<iostream>
using namespace std;
#define GT 1000
#define LT -1000
#define EQ 5000
int max(const int i,const int j,const int T[6][6],const int size);
int main()
{
//int a[6] = {0,5,4,2,1,3};
int a[6] = {0,1,2,3,4,5};

//没考虑数组中有相同元素的情况，其实也超简单

//更多数的，把6换一下就行.
//int size = sizeof(a) / 4;
int size = 6;
int T[6][6];
for(int i = 0;i < size;i++){
for(int j = 0 ; j < size;j++){
T[i][j] = 0;
}
}

//build relation table
for( i = 0;i < size;i++){
for(int j = i+1 ; j < size;j++){
if(a[i] > a[j]) T[i][j] = GT;
if(a[i] == a[j]) T[i][j] = EQ;
if(a[i] < a[j]) T[i][j] = LT;
}
}
for( i = 0;i < size;i++){
cout<<endl;
for(int j = 0;j < size;j++){
cout << T[i][j] <<"\t";
}
}
cout << endl;
cout << endl;

//dynamic programing
for( i = 0;i < size;i++)
T[i][i] = 1;
for( i = 0;i < size;i++){
for(int j = i+1 ; j < size;j++){
if(T[i][j] == GT)
T[i][j] = 0;
}
}

for(i = size-2 ;i >= 0;i--){
for(int j = i+1 ;j < size ;j++){
if(T[i][j] == LT){
//T[i][j] = max{A[j][K]|k=j...size-1};
T[i][j] = max(j,j,T,size) + 1;
}
}

}
for( i = 0;i < size;i++){
cout<<endl;
for(int j = 0;j < size;j++){
cout << T[i][j] <<"\t";
}
}

return 0;

}
int max(const int i,const int j,const int T[6][6],const int size){
/*
Return the max value of T[i][j....size-1];
*/
int max = T[i][j];
for(int k = j+1;k < size;k++){
max = max < T[i][k] ? T[i][k] : max;
}
return max;
}

cost: 0(n^3)

程序设计思想：

D.P

1。首先建立关系表：大小偏序关系。只有小于关系能走(上三角矩阵) . 对角线初始化为1.

2. 回溯：从上三角矩阵从下往上找最大值。

3. 上面程序并未给出子序列：只需在最终矩阵中找每行最大对应的元素，即为LIS中元素。

4. 最终可能有多条路径：因为可能存在多个LIS。

D.P

1。首先建立关系表：大小偏序关系。只有小于关系能走(上三角矩阵) . 对角线初始化为1.

2. 回溯：从上三角矩阵从下往上找最大值。

3. 上面程序并未给出子序列：只需在最终矩阵中找每行最大对应的元素，即为LIS中元素。

4. 最终可能有多条路径：因为可能存在多个LIS。

D.P

1。首先建立关系表：大小偏序关系。只有小于关系能走(上三角矩阵) . 对角线初始化为1.

2. 回溯：从上三角矩阵从下往上找最大值。

3. 上面程序并未给出子序列：只需在最终矩阵中找每行最大对应的元素，即为LIS中元素。

4. 最终可能有多条路径：因为可能存在多个LIS。

D.P

1。首先建立关系表：大小偏序关系。只有小于关系能走(上三角矩阵) . 对角线初始化为1.

2. 回溯：从上三角矩阵从下往上找最大值。

3. 上面程序并未给出子序列：只需在最终矩阵中找每行最大对应的元素，即为LIS中元素。

4. 最终可能有多条路径：因为可能存在多个LIS。

Plz enjoy!