LIS

求最大上升子序列（Longest Increasing Subsequence），动态规划中最基础的题目。

• 状态：D(k)，表示末尾下标为k的LIS的长度
• 状态转移方程：
  ![][piecewise]
  [piecewise]: http://latex.codecogs.com/svg.latex?D(k)=\begin{cases}max(D(j)+1),&A(j)%3CA(k),1\leqj\leqk-1\\1,&A(j)\ge%20A(k)\end{cases}

代码实现—O(N^2)

#include<stdio.h>
#define maxSize 20

int main(void)
{
    int n,i,j;
    int max;
    int a[maxSize];     //存储元素
    int d[maxSize];     //存储对应下标对应的LIS长度
    
    scanf("%d",&n);
    for(i=0;i<n;++i)
        scanf("%d",&a[i]);
    
    /*关键步骤，根据状态转移方程更新LIS数组d[]*/
    max=0;
    for(i=0;i<n;++i)
    {
        d[i]=1;
        for(j=0;j<i;++j)
            if(a[j]<a[i]&&d[j]+1>d[i])
                d[i]=d[j]+1;
        if(max<d[i])
            max=d[i];
    }   
    printf("%d",max);
    return 0;
}

代码实现—O(NlogN)

#include<stdio.h>
#define maxSize 20

int main(void)
{
    int stack[maxSize];     //利用栈进行记录
    int top=0;
    int i,temp,n;
    
    scanf("%d",&n);
    stack[0]=-1;        //输入值可能为0的特殊情况
    for(i=0;i<n;++i)
    {
        scanf("%d",&temp);
        if(temp>stack[top])
            stack[++top]=temp;
        /*利用二分法查找来更新栈*/
        else
        {
            int low=1,high=top;
            int mid;
            while(low<=high)
            {
                mid=(low+high)/2;
                if(temp>stack[mid])
                    low=mid+1;
                else
                    high=mid-1;
            }
            stack[mid]=temp;
        } 
    }
    printf("%d",top);       //栈的长度即为LIS长度 
    return 0;
}

参考

Slyar Home-姜楠
Slyar Home-姜楠