神马文学网最长非递增子集
来源：百度文库 编辑：神马文学网 时间：2024/04/28 05:39:34
#include
#define NUM 10
int a[NUM];
int b[NUM];//存放以a[i](0<=i<=a.length-1)为最后元素的最大递减子串的长度。
int k;//存放最大递减子串最后一个元素的下标
//求出b[i]中最大的值（即是最大递减子串的长度），并将其下标存在k中
int Max() {
int temp = 0;
for (int i = 0; i < NUM; i++) {
if (b[i] > temp) {
temp = b[i];
k = i;
}
}
return temp;
}
// 以a[i](0<=i<=a.length-1)为最后元素的最大递增子串的长度存到b[i]中
int Lis() {
b[0] = 1;//以a[0]为最后元素的子串只有a[0]，所以长度为1.
int k;
for (int i = 1; i < NUM; i++) {
k = 0;
for (int j = 0; j < i; j++) {
if (a[j] >= a[i] && k < b[j]) {
//比较所有小于a[i]并位于a[i]前面的最大子串的长度。比如6，2，5，3，那么以3结尾的最大子串长度
//等于：max{(大于3的元素有5，6)5的最大子串长度，6的最大子串长度}+1;
k = b[j];
}
}
b[i] = k + 1;
}
return Max();
}
//从小到大输出递减子串
void print(int index){
printf("%d ",a[index]);
for (int i = 0; i < index; i++) {
if (b[i] == b[index] - 1 && a[i] >= a[index]) {
print(i);
break;
}
}
}
void main(){
for(int i = 0; i < NUM; i++)
scanf("%d",&a[i]);
printf("最大非递增子串的长度为：%d\n",Lis());
printf("最大递增子串从小到大输出为：\n");
print(k);
}