最长递增子序列问题。
O(n^2)
DP。 练练手
#include <iostream>
using namespace std;
const int MAX = 1005;
int A[MAX],F[MAX];
int N, ans=-1;
int main()
{
int i,j;
scanf("%d", &N);
for(i=1; i<=N; ++i)
scanf("%d", &A[i]);
for(i=N; i>=1; --i){
F[i]=1;
for(j=i+1; j<=N; ++j)
if(A[j]>A[i] && F[j]+1>F[i])
F[i]=F[j]+1;
if(F[i]>ans)
ans = F[i];
}
printf("%d\n", ans);
return 0;
}O(nlgn)
开一个栈，每次取栈顶元素top和读到的元素temp做比较，如果temp > top 则将temp入栈；如果temp < top则二分查找栈中的比temp大的第1个数，并用temp替换它。 最长序列长度即为栈的大小top。
#include <iostream>
using namespace std;
const int MAX = 1005;
int stack[MAX];
int N, ans=-1;
int main(){
int i, tmp, top;
scanf("%d", &N);
stack[top=0]=-1;
for(i=1; i<=N; ++i){
scanf("%d", &tmp);
if(tmp>stack[top]){
stack[++top] = tmp;
}else{
int low=1, high=top;
while(low<=high){
int mid=(low+high)/2;
if(tmp>stack[mid])
low = mid+1;
else
high = mid-1;
}
stack[low]=tmp;
}
}
printf("%d\n", top);
return 0;
}
posted on 2011-03-10 11:21
小阮 阅读(236)
评论(0) 编辑 收藏 引用 所属分类:
POJ