最长非递增子集

#include<stdio.h>
#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);
}