1134 最長遞增子序列
基準時間限制:1 秒 空間限制:131072 KB 分值: 0 難度:基礎題 收藏 關注
給出長度為N的數組,找出這個數組的最長遞增子序列。(遞增子序列是指,子序列的元素是遞增的)
例如:5 1 6 8 2 4 5 10,最長遞增子序列是1 2 4 5 10。
Input
第1行:1個數N,N為序列的長度(2 <= N <= 50000)
第2 - N + 1行:每行1個數,對應序列的元素(-10^9 <= S[i] <= 10^9)
Output
輸出最長遞增子序列的長度。
Input示例
8
5
1
6
8
2
4
5
10
Output示例
5
解題思路:剛開始想着用常見的方法,後來逾時;優化後的代碼思路,以上測試資料作例,數組存放見如下
5
1
1 6
1 6 8
1 2 8
1 2 4
1 2 4 5
1 2 4 5 10
//逾時代碼
#include <iostream>
#include <stdio.h>
using namespace std;
int a[];
int dp[];
int main()
{
int n;
scanf("%d",&n);
for(int i=;i<=n;i++)
scanf("%d",&a[i]);
for(int i=;i<=n;i++)
dp[i]=;
for(int i=;i<=n;i++)
for(int j=;j<i;j++)
{
if(a[j]<=a[i])
dp[i]=max(dp[i],+dp[j]);
}
int imax=-;
for(int i=;i<=n;i++)
{
if(imax<dp[i])
imax=dp[i];
}
printf("%d\n",imax);
return ;
}
//優化代碼
#include <iostream>
#include <stdio.h>
using namespace std;
int a[];
int len1;
int find(int x)
{
int left=;
int right=len1;
int mid;
while(left<=right)
{
mid=(left+right)/;
if(a[mid]==x)
return mid;
else if(a[mid]>x)
right=mid-;
else
left=mid+;
}
return left;
}
int main()
{
int n;
scanf("%d",&n);
int k,t;
len1=;
for(int i=;i<=n;i++)
{
scanf("%d",&t);
k=find(t);
if(k<=len1)
a[k]=t;
else
a[++len1]=t;
}
printf("%d\n",len1);
return ;
}