求最大上升子序列（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;
}
参考
