算法导论笔记:15.4-6 最长单调递增子序列(LIS问题)

这道题完全懵了,网上的答案也不怎么看的懂,幸亏得到OI大佬的指点
大家可以先看一下这里,还有这篇详细的介绍

题目的提示还是很重要的

#include <stdio.h>

#define MAX 65535

int bsearch(int*,int);

int main(void)
{
    int num[9]={2,1,3,0,4,1,5,2,7};
    int result[9]={0};
    int log[9];
    for(int i=0;i<9;i++)
        log[i]=MAX;
    int len=1;//subsequence length
    for(int i=0;i<9;i++)
    {
        if(num[i]<log[0])
        {
            log[0]=num[i];
            if(len<=1)
            {
                result[0]=num[i];
            }
        }
        else
        {
            int j=bsearch(log,num[i]);
            log[j+1]=num[i];
            if(j+1>=len)
            {
                result[j+1]=result[j];
                result[j+1]=num[i];
            }
            if(j+1>=len)
                len++;
        }
    }
    printf("%d",len);
    for(int i=0;i<9;i++)
        printf("%d",result[i]);
    return 0;
}

int bsearch(int* base,int data)
{
    int left,mid,right;
    left=0;right=9;
    while(left<right)
    {
        mid=left+(right-left)/2;
        if(base[mid]>=data)
            right=mid;
        else
            left=mid+1;
    }
    if(base[left]<data&&base[left+1]>=data)
        return left;
    else
        return left-1;
}