原題；
題目描述
一個(gè)數(shù)的序列bi，當(dāng)b
1
< b
2
< ... < b
S
的時(shí)候，我們稱這個(gè)序列是上升的。對(duì)于給定的一個(gè)序列(a
1
, a
2
, ..., a
N
)，我們可以得到一些上升的子序列(a
i1
, a
i2
, ..., a
iK
)，這里1<= i
1
< i
2
< ... < i
K
<= N。比如，對(duì)于序列(1, 7, 3, 5, 9, 4, 8)，有它的一些上升子序列，如(1, 7), (3, 4, 8)等等。這些子序列中最長(zhǎng)的長(zhǎng)度是4，比如子序列(1, 3, 5, 8)。
你的任務(wù)，就是對(duì)于給定的序列，求出最長(zhǎng)上升子序列的長(zhǎng)度。
你的任務(wù)，就是對(duì)于給定的序列，求出最長(zhǎng)上升子序列的長(zhǎng)度。
輸入
輸入的第一行是序列的長(zhǎng)度N (1 <= N <= 1000)。第二行給出序列中的N個(gè)整數(shù)，這些整數(shù)的取值范圍都在0到10000。
輸出
最長(zhǎng)上升子序列的長(zhǎng)度。
示例輸入
7
1 7 3 5 9 4 8
示例輸出
4
?
?
分析：
dp第二彈~~~~~
?
?
源碼1——dp
#include<iostream>
#include<string.h>
using namespace std;
int num[1024];
int a[1024];
int p(int i)
{
if(i==1)
return a[1];
else
{
int max=0;
for(int j=1; j<i; j++)
{
if (a[j]==0)
a[j] = p(j);
if((a[j]>max)&&(num[i]>num[j]))
max=a[j];
}
a[i] = max+1;
}
return a[i];
}
int main()
{
int n;
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>num[i];
}
memset(a,0,sizeof(a));
a[1]=1;
p(n);
int max=0;
for (int i=1; i<=n; i++)
{
if (a[i]>max)
max=a[i];
}
cout<<max<<endl;
return 0;
}
?源碼2：又稱作LIS算法
#include<stdio.h>
int z[1007],dp[1007];
int main()
{
int n,i,j;
scanf("%d",&n);
for(i=1; i<=n; i++)
{
scanf("%d",&z[i]);
}
dp[1]=z[1];
int left,right,lenth=1;
for(j=2; j<=n; j++)
{
left=1;
right=lenth;
while(left<=right)
{
int mid=(left+right)/2;
if(dp[mid]<z[j])
{
left=mid+1;
}
else right=mid-1;
}
dp[left]=z[j];
if(left>lenth)
lenth++;
}
printf("%d\n",lenth);
return 0;
}
?
?
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長(zhǎng)非常感激您！手機(jī)微信長(zhǎng)按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
