LIS（Longest Increasing Subsequence）问题的解

问题：给出一个整数序列，求出最大递增序列（注意此处“序列”可以不连续排列，而“串”则必须连续排列）

思路：典型的动态规划问题，从头到尾遍历序列，当前遍历位置的最长递增序列是此处的上一处比当前遍历位置值小的那个数的最长递增序列加上当前遍历位置的值为后缀组成的序列（符号记忆能力不好真是伤不起，描述的时候一个变量都不想用）。

 

#include <stdio.h>  

int LIS(int a[10],int k,int r[10],int* pos)
{
    int prelow=0;
    if(k==0)
    {
        r[--*pos]=a[0];
        return 1;
    }

    if (a[k]>a[k-1])//如果当前值比前一个值大，那么记录当前位置的值，并返回长度
    {
        r[--*pos]=a[k];
        return LIS(a,k-1,r,pos)+1;
    }
    else
    {
        for (int j=k-2;j>=0;j--)//如果当前值比前一个值小，那么从当前位置倒数第二个位置开始遍历原序列，找到第一个比当前位置值小的数的位置j。此处可以通过对0到k-2这个序列进行二分查找，找到第一个比当前位置值小的数的位置，复杂度可以从O（n）降低到O（logn）
        {
            if (a[j]<a[k])
            {
                r[--*pos]=a[k];
                return LIS(a,j,r,pos)+1;//找到j的最小递增数组
            }
        }
    }

}

int main() 
{     
    int a[10]={3,7,5,4,6,8,5,7,6,7}; 
    int max=-1;

    for (int i=0;i<10;i++) //遍历原序列，找到小于i位置的最大递增序列
    {
        int r[10]={0};
        int pos=10;
        int c=LIS(a,i,r,&pos);//a是原序列，i是当前位置，r是为了记录遍历值的数组，pos是r的当前记录位置
        if (c>max)
        {
            max=c;
            for (int j=pos;j<10;j++)//打印出所有让max值发生变化的记录数组r，最后一个打印出的就是最大递增序列
            {
                printf("%d,",r[j]);
            }
            printf("\n");
        }
        
    }
    printf("max is %d\n",max);

    
    return 0;
}